pgpztrees.c

著名的加密软件的应用于电子邮件中

/*
* pgpZTrees.c
*
* Copyright (C) 1990-1993 Mark Adler, Richard B. Wales, Jean-loup Gailly,
* Kai Uwe Rommel and Igor Mandrichenko.
* Permission is granted to any individual or institution to use, copy,
* or redistribute this software so long as all of the original files
* are included, that it is not sold for profit, and that this copyright
* notice is retained.
*
* $Id: pgpZTrees.c,v 1.1.2.1 1997/06/07 09:51:11 mhw Exp $
*/

/*
* trees.c by Jean-loup Gailly
*
* This is a new version of im_ctree.c originally written by Richard B. Wales
* for the defunct implosion method.
*
* PURPOSE
*
* Encode various sets of source values using variable-length
* binary code trees.
*
* DISCUSSION
*
* The PKZIP "deflation" process uses several Huffman trees. The more
* common source values are represented by shorter bit sequences.
*
* Each code tree is stored in the ZIP file in a compressed form
* which is itself a Huffman encoding of the lengths of
* all the code strings (in ascending order by source values).
* The actual code strings are reconstructed from the lengths in
* the UNZIP process, as described in the "application note"
* (APPNOTE.TXT) distributed as part of PKWARE's PKZIP program.
*
* REFERENCES
*
	*	Lynch, Thomas J.
	*	Data Compression: Techniques and Applications, pp. 53-55.
	*	Lifetime Learning Publications, 1985. ISBN 0-534-03418-7.
*
	*	Storer, James A.
	*	Data Compression: Methods and Theory, pp. 49-50.
	*	Computer Science Press, 1988. ISBN 0-7167-8156-5.
*
	*	Sedgewick, R.
	*	Algorithms, p290.
	*	Addison-Wesley, 1983. ISBN 0-201-06672-6.
*
* INTERFACE
*
* void ct_init (void))
* Allocate the match buffer and initialize the various tables.
*
* void ct_tally (unsigned dist, unsigned lc);
* Save the match info and tally the frequency counts.
*
	*	long flush_block (char const *buf, word32 stored_len, int eof)
	*	Determine the best encoding for the current block: dynamic trees,
	*	static trees or store, and output the encoded block to the zip
	*	file. Returns the total compressed length for the file so far.
*
*/

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <ctype.h>
#include "pgpZip.h"

/* ===========================================================================
* Constants
*/

#define MAX_BITS 15
/* All codes must not exceed MAX_BITS bits */

#define MAX_BL_BITS 7
/* Bit length codes must not exceed MAX_BL_BITS bits */

#define LENGTH_CODES 29
/* number of length codes, not counting the special END_BLOCK code */

#define LITERALS 256
/* number of literal bytes 0..255 */

#define END_BLOCK 256
/* end of block literal code */

#define L_CODES (LITERALS+1+LENGTH_CODES)
/* number of Literal or Length codes, including the END_BLOCK code */

#define D_CODES 30
/* number of distance codes */

#define BL_CODES 19
/* number of codes used to transfer the bit lengths */


/* extra bits for each length code */
static int const near extra_lbits[LENGTH_CODES]
= {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0};

/* extra bits for each distance code */
static int const near extra_dbits[D_CODES]
= {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13};

/* extra bits for each bit length code */
static int const near extra_blbits[BL_CODES]
= {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};

#define STORED_BLOCK 0
#define STATIC_TREES 1
#define DYN_TREES 2
/* The three kinds of block type */

#ifndef LIT_BUFSIZE
# ifdef SMALL_MEM
	#	define LIT_BUFSIZE 0x2000
	#	else
	#	ifdef MEDIUM_MEM
	#	define LIT_BUFSIZE 0x4000
	#	else
	#	define LIT_BUFSIZE 0x8000
	#	endif
# endif
#endif
#define DIST_BUFSIZE LIT_BUFSIZE
/* Sizes of match buffers for literals/lengths and distances. There are
* 4 reasons for limiting LIT_BUFSIZE to < 64K:
* - frequencies can be kept in 16 bit counters
* - if compression is not successful for the first block, all input data is
* still in the window so we can still emit a stored block even when input
* comes from standard input. (This can also be done for all blocks if
* LIT_BUFSIZE is not greater than 32K.)
* - if compression is not successful for a file smaller than 64K, we can
* even emit a stored file instead of a stored block (saving 5 bytes).
* - creating new Huffman trees less frequently may not provide fast
*	adaptation to changes in the input data statistics. (Take for
*	example a binary file with poorly compressible code followed by
*	a highly compressible string table.) Smaller buffer sizes give
*	fast adaptation but have of course the overhead of transmitting trees
*	more frequently.
* - I can't count above 4
* The current code is general and allows DIST_BUFSIZE < LIT_BUFSIZE (to save
* memory at the expense of compression). Some optimizations would be possible
* if we rely on DIST_BUFSIZE == LIT_BUFSIZE.
*/

#define REP_3_6 16
/* repeat previous bit length 3-6 times (2 bits of repeat count) */

#define REPZ_3_10 17
/* repeat a zero length 3-10 times (3 bits of repeat count) */

#define REPZ_11_138 18
/* repeat a zero length 11-138 times (7 bits of repeat count) */

/* ===========================================================================
* Local data
*/

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

#define Freq fc.freq
#define Code fc.code
#define Dad dl.dad
#define Len dl.len

#define HEAP_SIZE (2*L_CODES+1)
/* maximum heap size */

static struct ct_data near dyn_ltree[HEAP_SIZE]; /* literal and length tree*/
static struct ct_data near dyn_dtree[2*D_CODES+1]; /* distance tree */

static struct ct_data near 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).
*/

static struct ct_data near static_dtree[D_CODES];
/* The static distance tree. (Actually a trivial tree since all codes use
* 5 bits.)
*/

static struct ct_data near bl_tree[2*BL_CODES+1];
/* Huffman tree for the bit lengths */

struct tree_desc {
struct ct_data near *dyn_tree; /* the dynamic tree */
struct ct_data near *static_tree; /* corresponding static tree or NULL */
	int	const near *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*/
};

static struct tree_desc near l_desc =
{dyn_ltree, static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS, 0};

static struct tree_desc near d_desc =
{dyn_dtree, static_dtree, extra_dbits, 0, D_CODES, MAX_BITS, 0};

static struct tree_desc near bl_desc =
{bl_tree, NULL, extra_blbits, 0,	BL_CODES, MAX_BL_BITS, 0};


static word16 near bl_count[MAX_BITS+1];
/* number of codes at each bit length for an optimal tree */

static byte const near bl_order[BL_CODES]
= {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
/* The lengths of the bit length codes are sent in order of decreasing
* probability, to avoid transmitting the lengths for unused bit length codes.
*/

static int near heap[2*L_CODES+1]; /* heap used to build the Huffman trees */
static int heap_len; /* number of elements in the heap */
static 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.
*/

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

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

static byte 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.
*/

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

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

#ifndef DYN_ALLOC
static byte far l_buf[LIT_BUFSIZE]; /* buffer for literals/lengths */
static word16 far d_buf[DIST_BUFSIZE]; /* buffer for distances */
#else
static byte far *l_buf;
static word16 far *d_buf;
#endif

static byte near 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.
*/

static unsigned last_lit; /* running index in l_buf */
static unsigned last_dist; /* running index in d_buf */
static unsigned last_flags; /* running index in flag_buf */
static byte flags; /* current flags not yet saved in flag_buf */
static byte 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.
*/

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

static word32 compressed_len; /* total bit length of compressed file */

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

#ifdef ZIPDEBUG
extern word32 bits_sent; /* bit length of the compressed data */
extern word32 isize; /* byte length of input file */
#endif

extern long block_start; /* window offset of current block */
extern unsigned near strstart; /* window offset of current string */

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

static void init_block(void);
static void pqdownheap(struct ct_data near *tree, int k);
static void gen_bitlen(struct tree_desc near *desc);
static void gen_codes(struct ct_data near *tree, int max_code);
static void build_tree(struct tree_desc near *desc);
static void scan_tree(struct ct_data near *tree, int max_code);
static void send_tree(struct ct_data near *tree, int max_code);
static int build_bl_tree(void);
static void send_all_trees(int lcodes, int dcodes, int blcodes);
static void compress_block(struct ct_data near *ltree,
struct ct_data near *dtree);


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

#else /* ZIPDEBUG */
# define send_code(c, tree) \
{ if (verbose > 1) fprintf(stderr,"\ncd %3d ",(c)); \
send_bits(tree[c].Code, tree[c].Len); }
#endif

#define d_code(dist) \
((dist) < 256 ? dist_code[dist] : 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 */

/* ===========================================================================
* Reverse k low-order bits in a word. Not speed-critical.
*/
static unsigned
bit_reverse(unsigned value, int len)
	{
			unsigned result = 0;

			do {
				 result <<= 1;
				 result |= value & 1;
				 value >>= 1;
			} while (--len);
			return result;
	}

/* ===========================================================================
* Allocate the match buffer and initialize the various tables.
*/
int
ct_init(void)
	{
		int n;	/* iterates over tree elements */
		int bits;	/* bit counter */
int length; /* length value */
int code; /* code value */
int dist; /* distance index */

compressed_len = input_len = 0L;

#ifdef DYN_ALLOC
/* Allocate the buffers */
d_buf = (word16 far *)fcalloc(DIST_BUFSIZE, sizeof(word16));
if (d_buf == NULL)
			return -1;
		l_buf = (byte far *)fcalloc(LIT_BUFSIZE/2, 2);
		/* Avoid using the value 64K on 16 bit machines */
		if (l_buf == NULL) {
			fcfree(d_buf);
			return -1;
		}
	/*	if (l_buf == NULL || d_buf == NULL) error("ct_init: out of memory"); */
#endif
		/* Initialize the counts for the first block */
		init_block();

	/* The following initializes constant data - it may be skipped */
	if (static_dtree[0].Len != 0) return 0; /* ct_init already called */

	/* Initialize the mapping length (0..255) -> length code (0..28) */
	length = 0;
		for (code = 0; code < LENGTH_CODES-1; code++) {
			base_length[code] = length;
			for (n = 0; n < (1<<extra_lbits[code]); n++) {
			length_code[length++] = (byte)code;
			}
		}
		ZipAssert (length == 256, "ct_init: length != 256");