}	if (s == NULL) {		c = 0xffffffffL;	} else {		c = crc;		if (n)			do {				c = crc_32_tab[((int) c ^ (*s++)) & 0xff] ^ (c >> 8);			} while (--n);	}	crc = c;	return c ^ 0xffffffffL;		/* (instead of ~c for 64-bit machines) */}/* bits.c -- output variable-length bit strings * Copyright (C) 1992-1993 Jean-loup Gailly * This is free software; you can redistribute it and/or modify it under the * terms of the GNU General Public License, see the file COPYING. *//* *  PURPOSE * *      Output variable-length bit strings. Compression can be done *      to a file or to memory. (The latter is not supported in this version.) * *  DISCUSSION * *      The PKZIP "deflate" file format interprets compressed file data *      as a sequence of bits.  Multi-bit strings in the file may cross *      byte boundaries without restriction. * *      The first bit of each byte is the low-order bit. * *      The routines in this file allow a variable-length bit value to *      be output right-to-left (useful for literal values). For *      left-to-right output (useful for code strings from the tree routines), *      the bits must have been reversed first with bi_reverse(). * *      For in-memory compression, the compressed bit stream goes directly *      into the requested output buffer. The input data is read in blocks *      by the mem_read() function. The buffer is limited to 64K on 16 bit *      machines. * *  INTERFACE * *      void bi_init (FILE *zipfile) *          Initialize the bit string routines. * *      void send_bits (int value, int length) *          Write out a bit string, taking the source bits right to *          left. * *      int bi_reverse (int value, int length) *          Reverse the bits of a bit string, taking the source bits left to *          right and emitting them right to left. * *      void bi_windup (void) *          Write out any remaining bits in an incomplete byte. * *      void copy_block(char *buf, unsigned len, int header) *          Copy a stored block to the zip file, storing first the length and *          its one's complement if requested. * *//* =========================================================================== * Local data used by the "bit string" routines. */static file_t zfile;				/* output gzip file */static unsigned short bi_buf;/* Output buffer. bits are inserted starting at the bottom (least significant * bits). */#define Buf_size (8 * 2*sizeof(char))/* Number of bits used within bi_buf. (bi_buf might be implemented on * more than 16 bits on some systems.) */static int bi_valid;/* Current input function. Set to mem_read for in-memory compression */#ifdef DEBUGulg bits_sent;					/* bit length of the compressed data */#endif/* =========================================================================== * Initialize the bit string routines. */static void bi_init(file_t zipfile){	zfile = zipfile;	bi_buf = 0;	bi_valid = 0;#ifdef DEBUG	bits_sent = 0L;#endif	/* Set the defaults for file compression. They are set by memcompress	 * for in-memory compression.	 */	if (zfile != NO_FILE) {		read_buf = file_read;	}}/* =========================================================================== * Send a value on a given number of bits. * IN assertion: length <= 16 and value fits in length bits. */static void send_bits(int value, int length){#ifdef DEBUG	Tracev((stderr, " l %2d v %4x ", length, value));	Assert(length > 0 && length <= 15, "invalid length");	bits_sent += (ulg) length;#endif	/* If not enough room in bi_buf, use (valid) bits from bi_buf and	 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))	 * unused bits in value.	 */	if (bi_valid > (int) Buf_size - length) {		bi_buf |= (value << bi_valid);		put_short(bi_buf);		bi_buf = (ush) value >> (Buf_size - bi_valid);		bi_valid += length - Buf_size;	} else {		bi_buf |= value << bi_valid;		bi_valid += length;	}}/* =========================================================================== * Reverse the first len bits of a code, using straightforward code (a faster * method would use a table) * IN assertion: 1 <= len <= 15 */static 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. */static void bi_windup(){	if (bi_valid > 8) {		put_short(bi_buf);	} else if (bi_valid > 0) {		put_byte(bi_buf);	}	bi_buf = 0;	bi_valid = 0;#ifdef DEBUG	bits_sent = (bits_sent + 7) & ~7;#endif}/* =========================================================================== * Copy a stored block to the zip file, storing first the length and its * one's complement if requested. */static void copy_block(char *buf, unsigned len, int header){	bi_windup();				/* align on byte boundary */	if (header) {		put_short((ush) len);		put_short((ush) ~ len);#ifdef DEBUG		bits_sent += 2 * 16;#endif	}#ifdef DEBUG	bits_sent += (ulg) len << 3;#endif	while (len--) {		put_byte(*buf++);	}}/* deflate.c -- compress data using the deflation algorithm * Copyright (C) 1992-1993 Jean-loup Gailly * This is free software; you can redistribute it and/or modify it under the * terms of the GNU General Public License, see the file COPYING. *//* *  PURPOSE * *      Identify new text as repetitions of old text within a fixed- *      length sliding window trailing behind the new text. * *  DISCUSSION * *      The "deflation" process depends on being able to identify portions *      of the input text which are identical to earlier input (within a *      sliding window trailing behind the input currently being processed). * *      The most straightforward technique turns out to be the fastest for *      most input files: try all possible matches and select the longest. *      The key feature of this algorithm is that insertions into the string *      dictionary are very simple and thus fast, and deletions are avoided *      completely. Insertions are performed at each input character, whereas *      string matches are performed only when the previous match ends. So it *      is preferable to spend more time in matches to allow very fast string *      insertions and avoid deletions. The matching algorithm for small *      strings is inspired from that of Rabin & Karp. A brute force approach *      is used to find longer strings when a small match has been found. *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze *      (by Leonid Broukhis). *         A previous version of this file used a more sophisticated algorithm *      (by Fiala and Greene) which is guaranteed to run in linear amortized *      time, but has a larger average cost, uses more memory and is patented. *      However the F&G algorithm may be faster for some highly redundant *      files if the parameter max_chain_length (described below) is too large. * *  ACKNOWLEDGEMENTS * *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and *      I found it in 'freeze' written by Leonid Broukhis. *      Thanks to many info-zippers for bug reports and testing. * *  REFERENCES * *      APPNOTE.TXT documentation file in PKZIP 1.93a distribution. * *      A description of the Rabin and Karp algorithm is given in the book *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252. * *      Fiala,E.R., and Greene,D.H. *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595 * *  INTERFACE * *      void lm_init (int pack_level, ush *flags) *          Initialize the "longest match" routines for a new file * *      ulg deflate (void) *          Processes a new input file and return its compressed length. Sets *          the compressed length, crc, deflate flags and internal file *          attributes. *//* =========================================================================== * Configuration parameters *//* Compile with MEDIUM_MEM to reduce the memory requirements or * with SMALL_MEM to use as little memory as possible. Use BIG_MEM if the * entire input file can be held in memory (not possible on 16 bit systems). * Warning: defining these symbols affects HASH_BITS (see below) and thus * affects the compression ratio. The compressed output * is still correct, and might even be smaller in some cases. */#ifdef SMALL_MEM#   define HASH_BITS  13		/* Number of bits used to hash strings */#endif#ifdef MEDIUM_MEM#   define HASH_BITS  14#endif#ifndef HASH_BITS#   define HASH_BITS  15   /* For portability to 16 bit machines, do not use values above 15. */#endif/* To save space (see unlzw.c), we overlay prev+head with tab_prefix and * window with tab_suffix. Check that we can do this: */#if (WSIZE<<1) > (1<<BITS)#  error cannot overlay window with tab_suffix and prev with tab_prefix0#endif#if HASH_BITS > BITS-1#  error cannot overlay head with tab_prefix1#endif#define HASH_SIZE (unsigned)(1<<HASH_BITS)#define HASH_MASK (HASH_SIZE-1)#define WMASK     (WSIZE-1)/* HASH_SIZE and WSIZE must be powers of two */#define NIL 0/* Tail of hash chains */#define FAST 4#define SLOW 2/* speed options for the general purpose bit flag */#ifndef TOO_FAR#  define TOO_FAR 4096#endif/* Matches of length 3 are discarded if their distance exceeds TOO_FAR *//* =========================================================================== * Local data used by the "longest match" routines. */typedef ush Pos;typedef unsigned IPos;/* A Pos is an index in the character window. We use short instead of int to * save space in the various tables. IPos is used only for parameter passing. *//* DECLARE(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+BSZ if SMALL_MEM (the code would * be less efficient). *//* DECLARE(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. *//* DECLARE(Pos, head, 1<<HASH_BITS); *//* Heads of the hash chains or NIL. */static const ulg window_size = (ulg) 2 * WSIZE;/* window size, 2*WSIZE except for MMAP or BIG_MEM, where it is the * input file length plus MIN_LOOKAHEAD. */static long block_start;/* window position at the beginning of the current output block. Gets * negative when the window is moved backwards. */static unsigned ins_h;			/* hash index of string to be inserted */#define H_SHIFT  ((HASH_BITS+MIN_MATCH-1)/MIN_MATCH)/* Number of bits by which ins_h and del_h must be shifted at each * input step. It must be such that after MIN_MATCH steps, the oldest * byte no longer takes part in the hash key, that is: *   H_SHIFT * MIN_MATCH >= HASH_BITS */static 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. */static unsigned strstart;			/* start of string to insert */static unsigned match_start;		/* start of matching string */static int eofile;				/* flag set at end of input file */static unsigned lookahead;		/* number of valid bytes ahead in window */static const unsigned max_chain_length=4096;/* To speed up deflation, hash chains are never searched beyond this length. * A higher limit improves compression ratio but degrades the speed. */static const unsigned int max_lazy_match=258;/* 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. */#define max_insert_length  max_lazy_match/* Insert new strings in the hash table only if the match length * is not greater than this length. This saves time but degrades compression. * max_insert_length is used only for compression levels <= 3. */static const unsigned good_match=32;/* Use a faster search when the previous match is longer than this *//* Values for max_lazy_match, good_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. */static const int nice_match=258;			/* Stop searching when current match exceeds this *//* 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. */#define EQUAL 0/* result of memcmp for equal strings *//* =========================================================================== *  Prototypes for local functions. */static void fill_window (void);static int longest_match (IPos cur_match);