X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=archival%2Fgzip.c;h=12c1df242a99e627cca25c0d56c7f2f564a8b37d;hb=266bec8ba76898c5602e54fb3460c4af42f38af0;hp=9411e17a9c148e89d1c8ae90c728be976641e0f0;hpb=fe42d17318fffed53f02617fd668d896000bdd28;p=oweals%2Fbusybox.git diff --git a/archival/gzip.c b/archival/gzip.c index 9411e17a9..12c1df242 100644 --- a/archival/gzip.c +++ b/archival/gzip.c @@ -13,46 +13,98 @@ * files as well as stdin/stdout, and to generally behave itself wrt * command line handling. * - * Licensed under GPLv2 or later, see file LICENSE in this tarball for details. + * Licensed under GPLv2 or later, see file LICENSE in this source tree. */ - -/* big objects in bss: - * 00000020 b bl_count - * 00000074 b base_length - * 00000078 b base_dist - * 00000078 b static_dtree - * 0000009c b bl_tree - * 000000f4 b dyn_dtree - * 00000100 b length_code - * 00000200 b dist_code - * 0000023d b depth - * 00000400 b flag_buf - * 0000047a b heap - * 00000480 b static_ltree - * 000008f4 b dyn_ltree - */ - /* TODO: full support for -v for DESKTOP * "/usr/bin/gzip -v a bogus aa" should say: a: 85.1% -- replaced with a.gz gzip: bogus: No such file or directory aa: 85.1% -- replaced with aa.gz */ - -#include "busybox.h" - +//config:config GZIP +//config: bool "gzip (17 kb)" +//config: default y +//config: help +//config: gzip is used to compress files. +//config: It's probably the most widely used UNIX compression program. +//config: +//config:config FEATURE_GZIP_LONG_OPTIONS +//config: bool "Enable long options" +//config: default y +//config: depends on GZIP && LONG_OPTS +//config: +//config:config GZIP_FAST +//config: int "Trade memory for speed (0:small,slow - 2:fast,big)" +//config: default 0 +//config: range 0 2 +//config: depends on GZIP +//config: help +//config: Enable big memory options for gzip. +//config: 0: small buffers, small hash-tables +//config: 1: larger buffers, larger hash-tables +//config: 2: larger buffers, largest hash-tables +//config: Larger models may give slightly better compression +//config: +//config:config FEATURE_GZIP_LEVELS +//config: bool "Enable compression levels" +//config: default n +//config: depends on GZIP +//config: help +//config: Enable support for compression levels 4-9. The default level +//config: is 6. If levels 1-3 are specified, 4 is used. +//config: If this option is not selected, -N options are ignored and -9 +//config: is used. +//config: +//config:config FEATURE_GZIP_DECOMPRESS +//config: bool "Enable decompression" +//config: default y +//config: depends on GZIP || GUNZIP || ZCAT +//config: help +//config: Enable -d (--decompress) and -t (--test) options for gzip. +//config: This will be automatically selected if gunzip or zcat is +//config: enabled. + +//applet:IF_GZIP(APPLET(gzip, BB_DIR_BIN, BB_SUID_DROP)) + +//kbuild:lib-$(CONFIG_GZIP) += gzip.o + +//usage:#define gzip_trivial_usage +//usage: "[-cfk" IF_FEATURE_GZIP_DECOMPRESS("dt") IF_FEATURE_GZIP_LEVELS("123456789") "] [FILE]..." +//usage:#define gzip_full_usage "\n\n" +//usage: "Compress FILEs (or stdin)\n" +//usage: IF_FEATURE_GZIP_LEVELS( +//usage: "\n -1..9 Compression level" +//usage: ) +//usage: IF_FEATURE_GZIP_DECOMPRESS( +//usage: "\n -d Decompress" +//usage: "\n -t Test file integrity" +//usage: ) +//usage: "\n -c Write to stdout" +//usage: "\n -f Force" +//usage: "\n -k Keep input files" +//usage: +//usage:#define gzip_example_usage +//usage: "$ ls -la /tmp/busybox*\n" +//usage: "-rw-rw-r-- 1 andersen andersen 1761280 Apr 14 17:47 /tmp/busybox.tar\n" +//usage: "$ gzip /tmp/busybox.tar\n" +//usage: "$ ls -la /tmp/busybox*\n" +//usage: "-rw-rw-r-- 1 andersen andersen 554058 Apr 14 17:49 /tmp/busybox.tar.gz\n" + +#include "libbb.h" +#include "bb_archive.h" /* =========================================================================== */ //#define DEBUG 1 /* Diagnostic functions */ #ifdef DEBUG -# define Assert(cond,msg) {if(!(cond)) bb_error_msg(msg);} +static int verbose; +# define Assert(cond,msg) { if (!(cond)) bb_error_msg(msg); } # define Trace(x) fprintf x -# define Tracev(x) {if (verbose) fprintf x ;} -# define Tracevv(x) {if (verbose > 1) fprintf x ;} -# define Tracec(c,x) {if (verbose && (c)) fprintf x ;} -# define Tracecv(c,x) {if (verbose > 1 && (c)) fprintf x ;} +# define Tracev(x) {if (verbose) fprintf x; } +# define Tracevv(x) {if (verbose > 1) fprintf x; } +# define Tracec(c,x) {if (verbose && (c)) fprintf x; } +# define Tracecv(c,x) {if (verbose > 1 && (c)) fprintf x; } #else # define Assert(cond,msg) # define Trace(x) @@ -62,12 +114,19 @@ aa: 85.1% -- replaced with aa.gz # define Tracecv(c,x) #endif - /* =========================================================================== */ -#define SMALL_MEM +#if CONFIG_GZIP_FAST == 0 +# define SMALL_MEM +#elif CONFIG_GZIP_FAST == 1 +# define MEDIUM_MEM +#elif CONFIG_GZIP_FAST == 2 +# define BIG_MEM +#else +# error "Invalid CONFIG_GZIP_FAST value" +#endif -#ifndef INBUFSIZ +#ifndef INBUFSIZ # ifdef SMALL_MEM # define INBUFSIZ 0x2000 /* input buffer size */ # else @@ -75,7 +134,7 @@ aa: 85.1% -- replaced with aa.gz # endif #endif -#ifndef OUTBUFSIZ +#ifndef OUTBUFSIZ # ifdef SMALL_MEM # define OUTBUFSIZ 8192 /* output buffer size */ # else @@ -150,7 +209,6 @@ aa: 85.1% -- replaced with aa.gz # define MAX_SUFFIX 30 #endif - /* =========================================================================== * 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 @@ -159,15 +217,14 @@ aa: 85.1% -- replaced with aa.gz * 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 */ +# define HASH_BITS 13 /* Number of bits used to hash strings */ #endif #ifdef MEDIUM_MEM -# define HASH_BITS 14 +# define HASH_BITS 14 #endif #ifndef HASH_BITS -# define HASH_BITS 15 +# define HASH_BITS 15 /* For portability to 16 bit machines, do not use values above 15. */ #endif @@ -180,7 +237,6 @@ aa: 85.1% -- replaced with aa.gz #endif /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ - /* =========================================================================== * These types are not really 'char', 'short' and 'long' */ @@ -201,6 +257,8 @@ enum { * input file length plus MIN_LOOKAHEAD. */ +#if !ENABLE_FEATURE_GZIP_LEVELS + 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. @@ -232,46 +290,20 @@ enum { * For deflate_fast() (levels <= 3) good is ignored and lazy has a different * meaning. */ +#endif /* ENABLE_FEATURE_GZIP_LEVELS */ }; +struct globals { +/* =========================================================================== */ +/* global buffers, allocated once */ -struct global1 { - - lng block_start; - -/* window position at the beginning of the current output block. Gets - * negative when the window is moved backwards. - */ - 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 - */ - - unsigned 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 */ - unsigned lookahead; /* number of valid bytes ahead in window */ - -/* =========================================================================== - */ #define DECLARE(type, array, size) \ type * array #define ALLOC(type, array, size) \ - array = xzalloc((size_t)(((size)+1L)/2) * 2*sizeof(type)); + array = xzalloc((size_t)(((size)+1L)/2) * 2*sizeof(type)) #define FREE(array) \ do { free(array); array = NULL; } while (0) - /* global buffers */ - /* buffer for literals or lengths */ /* DECLARE(uch, l_buf, LIT_BUFSIZE); */ DECLARE(uch, l_buf, INBUFSIZ); @@ -301,6 +333,46 @@ struct global1 { /* DECLARE(Pos, head, 1<= HASH_BITS + */ +#define H_SHIFT ((HASH_BITS+MIN_MATCH-1) / MIN_MATCH) + +/* Length of the best match at previous step. Matches not greater than this + * are discarded. This is used in the lazy match evaluation. + */ + unsigned prev_length; + + unsigned strstart; /* start of string to insert */ + unsigned match_start; /* start of matching string */ + unsigned lookahead; /* number of valid bytes ahead in window */ + /* number of input bytes */ ulg isize; /* only 32 bits stored in .gz file */ @@ -312,41 +384,35 @@ struct global1 { unsigned insize; /* valid bytes in l_buf */ #endif unsigned outcnt; /* bytes in output buffer */ - smallint eofile; /* flag set at end of input file */ /* =========================================================================== * Local data used by the "bit string" routines. */ - unsigned short bi_buf; - /* Output buffer. bits are inserted starting at the bottom (least significant * bits). */ + unsigned bi_buf; /* was unsigned short */ #undef BUF_SIZE -#define BUF_SIZE (8 * sizeof(G1.bi_buf)) +#define BUF_SIZE (int)(8 * sizeof(G1.bi_buf)) + /* Number of bits used within bi_buf. (bi_buf might be implemented on * more than 16 bits on some systems.) */ - - int bi_valid; - -/* Current input function. Set to mem_read for in-memory compression */ + unsigned bi_valid; #ifdef DEBUG - ulg bits_sent; /* bit length of the compressed data */ + ulg bits_sent; /* bit length of the compressed data */ +# define DEBUG_bits_sent(v) (void)(G1.bits_sent v) +#else +# define DEBUG_bits_sent(v) ((void)0) #endif - - uint32_t *crc_32_tab; - uint32_t crc; /* shift register contents */ }; -extern struct global1 *ptr_to_globals; #define G1 (*(ptr_to_globals - 1)) - /* =========================================================================== * Write the output buffer outbuf[0..outcnt-1] and update bytes_out. * (used for the compressed data only) @@ -360,64 +426,89 @@ static void flush_outbuf(void) G1.outcnt = 0; } - /* =========================================================================== */ /* put_8bit is used for the compressed output */ #define put_8bit(c) \ do { \ G1.outbuf[G1.outcnt++] = (c); \ - if (G1.outcnt == OUTBUFSIZ) flush_outbuf(); \ + if (G1.outcnt == OUTBUFSIZ) \ + flush_outbuf(); \ } while (0) /* Output a 16 bit value, lsb first */ static void put_16bit(ush w) { - if (G1.outcnt < OUTBUFSIZ - 2) { - G1.outbuf[G1.outcnt++] = w; - G1.outbuf[G1.outcnt++] = w >> 8; - } else { - put_8bit(w); - put_8bit(w >> 8); + /* GCC 4.2.1 won't optimize out redundant loads of G1.outcnt + * (probably because of fear of aliasing with G1.outbuf[] + * stores), do it explicitly: + */ + unsigned outcnt = G1.outcnt; + uch *dst = &G1.outbuf[outcnt]; + +#if BB_UNALIGNED_MEMACCESS_OK && BB_LITTLE_ENDIAN + if (outcnt < OUTBUFSIZ-2) { + /* Common case */ + ush *dst16 = (void*) dst; + *dst16 = w; /* unaligned LSB 16-bit store */ + G1.outcnt = outcnt + 2; + return; } + *dst = (uch)w; + w >>= 8; + G1.outcnt = ++outcnt; +#else + *dst = (uch)w; + w >>= 8; + if (outcnt < OUTBUFSIZ-2) { + /* Common case */ + dst[1] = w; + G1.outcnt = outcnt + 2; + return; + } + G1.outcnt = ++outcnt; +#endif + + /* Slowpath: we will need to do flush_outbuf() */ + if (outcnt == OUTBUFSIZ) + flush_outbuf(); /* here */ + put_8bit(w); /* or here */ } +#define OPTIMIZED_PUT_32BIT (CONFIG_GZIP_FAST > 0 && BB_UNALIGNED_MEMACCESS_OK && BB_LITTLE_ENDIAN) static void put_32bit(ulg n) { + if (OPTIMIZED_PUT_32BIT) { + unsigned outcnt = G1.outcnt; + if (outcnt < OUTBUFSIZ-4) { + /* Common case */ + ulg *dst32 = (void*) &G1.outbuf[outcnt]; + *dst32 = n; /* unaligned LSB 32-bit store */ + //bb_error_msg("%p", dst32); // store alignment debugging + G1.outcnt = outcnt + 4; + return; + } + } put_16bit(n); put_16bit(n >> 16); } - -/* =========================================================================== - * Clear input and output buffers - */ -static void clear_bufs(void) +static ALWAYS_INLINE void flush_outbuf_if_32bit_optimized(void) { - G1.outcnt = 0; -#ifdef DEBUG - G1.insize = 0; -#endif - G1.isize = 0; + /* If put_32bit() performs 32bit stores && it is used in send_bits() */ + if (OPTIMIZED_PUT_32BIT && BUF_SIZE > 16) + flush_outbuf(); } - /* =========================================================================== * Run a set of bytes through the crc shift register. If s is a NULL * pointer, then initialize the crc shift register contents instead. * Return the current crc in either case. */ -static uint32_t updcrc(uch * s, unsigned n) +static void updcrc(uch * s, unsigned n) { - uint32_t c = G1.crc; - while (n) { - c = G1.crc_32_tab[(uch)(c ^ *s++)] ^ (c >> 8); - n--; - } - G1.crc = c; - return c; + G1.crc = crc32_block_endian0(G1.crc, s, n, global_crc32_table /*G1.crc_32_tab*/); } - /* =========================================================================== * Read a new buffer from the current input file, perform end-of-line * translation, and update the crc and input file size. @@ -438,34 +529,45 @@ static unsigned file_read(void *buf, unsigned size) return len; } - /* =========================================================================== * 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) +static void send_bits(unsigned value, unsigned length) { + unsigned new_buf; + #ifdef DEBUG Tracev((stderr, " l %2d v %4x ", length, value)); Assert(length > 0 && length <= 15, "invalid length"); - G1.bits_sent += length; + DEBUG_bits_sent(+= 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 (G1.bi_valid > (int) BUF_SIZE - length) { - G1.bi_buf |= (value << G1.bi_valid); - put_16bit(G1.bi_buf); - G1.bi_buf = (ush) value >> (BUF_SIZE - G1.bi_valid); - G1.bi_valid += length - BUF_SIZE; - } else { - G1.bi_buf |= value << G1.bi_valid; - G1.bi_valid += length; + BUILD_BUG_ON(BUF_SIZE != 32 && BUF_SIZE != 16); + + new_buf = G1.bi_buf | (value << G1.bi_valid); + /* NB: the above may sometimes do "<< 32" shift (undefined) + * if check below is changed to "length > BUF_SIZE" instead of >= */ + length += G1.bi_valid; + + /* If bi_buf is full */ + if (length >= BUF_SIZE) { + /* ...use (valid) bits from bi_buf and + * (BUF_SIZE - bi_valid) bits from value, + * leaving (width - (BUF_SIZE-bi_valid)) unused bits in value. + */ + value >>= (BUF_SIZE - G1.bi_valid); + if (BUF_SIZE == 32) { + put_32bit(new_buf); + } else { /* 16 */ + put_16bit(new_buf); + } + new_buf = value; + length -= BUF_SIZE; } + G1.bi_buf = new_buf; + G1.bi_valid = length; } - /* =========================================================================== * Reverse the first len bits of a code, using straightforward code (a faster * method would use a table) @@ -483,25 +585,24 @@ static unsigned bi_reverse(unsigned code, int len) } } - /* =========================================================================== * Write out any remaining bits in an incomplete byte. */ static void bi_windup(void) { - if (G1.bi_valid > 8) { - put_16bit(G1.bi_buf); - } else if (G1.bi_valid > 0) { - put_8bit(G1.bi_buf); + unsigned bits = G1.bi_buf; + int cnt = G1.bi_valid; + + while (cnt > 0) { + put_8bit(bits); + bits >>= 8; + cnt -= 8; } G1.bi_buf = 0; G1.bi_valid = 0; -#ifdef DEBUG - G1.bits_sent = (G1.bits_sent + 7) & ~7; -#endif + DEBUG_bits_sent(= (G1.bits_sent + 7) & ~7); } - /* =========================================================================== * Copy a stored block to the zip file, storing first the length and its * one's complement if requested. @@ -511,21 +612,19 @@ static void copy_block(char *buf, unsigned len, int header) bi_windup(); /* align on byte boundary */ if (header) { - put_16bit(len); - put_16bit(~len); -#ifdef DEBUG - G1.bits_sent += 2 * 16; -#endif + unsigned v = ((uint16_t)len) | ((~len) << 16); + put_32bit(v); + DEBUG_bits_sent(+= 2 * 16); } -#ifdef DEBUG - G1.bits_sent += (ulg) len << 3; -#endif + DEBUG_bits_sent(+= (ulg) len << 3); while (len--) { put_8bit(*buf++); } + /* The above can 32-bit misalign outbuf */ + if (G1.outcnt & 3) /* syscalls are expensive, is it really misaligned? */ + flush_outbuf_if_32bit_optimized(); } - /* =========================================================================== * Fill the window when the lookahead becomes insufficient. * Updates strstart and lookahead, and sets eofile if end of input file. @@ -583,7 +682,12 @@ static void fill_window(void) } } } - +/* Both users fill window with the same loop: */ +static void fill_window_if_needed(void) +{ + while (G1.lookahead < MIN_LOOKAHEAD && !G1.eofile) + fill_window(); +} /* =========================================================================== * Set match_start to the longest match starting at the given string and @@ -633,10 +737,12 @@ static int longest_match(IPos cur_match) /* Skip to next match if the match length cannot increase * or if the match length is less than 2: */ - if (match[best_len] != scan_end || - match[best_len - 1] != scan_end1 || - *match != *scan || *++match != scan[1]) + if (match[best_len] != scan_end + || match[best_len - 1] != scan_end1 + || *match != *scan || *++match != scan[1] + ) { continue; + } /* The check at best_len-1 can be removed because it will be made * again later. (This heuristic is not always a win.) @@ -672,7 +778,6 @@ static int longest_match(IPos cur_match) return best_len; } - #ifdef DEBUG /* =========================================================================== * Check that the match at match_start is indeed a match. @@ -687,7 +792,7 @@ static void check_match(IPos start, IPos match, int length) if (verbose > 1) { bb_error_msg("\\[%d,%d]", start - match, length); do { - putc(G1.window[start++], stderr); + bb_putchar_stderr(G1.window[start++]); } while (--length != 0); } } @@ -769,26 +874,24 @@ static void check_match(IPos start, IPos match, int length) #define BL_CODES 19 /* number of codes used to transfer the bit lengths */ -typedef uch extra_bits_t; - /* extra bits for each length code */ -static const extra_bits_t extra_lbits[LENGTH_CODES]= { +static const uint8_t extra_lbits[LENGTH_CODES] ALIGN1 = { 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 const extra_bits_t extra_dbits[D_CODES] = { +static const uint8_t extra_dbits[D_CODES] ALIGN1 = { 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 const extra_bits_t extra_blbits[BL_CODES] = { +static const uint8_t extra_blbits[BL_CODES] ALIGN1 = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7 }; /* number of codes at each bit length for an optimal tree */ -static const uch bl_order[BL_CODES] = { +static const uint8_t bl_order[BL_CODES] ALIGN1 = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 }; #define STORED_BLOCK 0 @@ -862,14 +965,14 @@ typedef struct ct_data { typedef struct tree_desc { ct_data *dyn_tree; /* the dynamic tree */ ct_data *static_tree; /* corresponding static tree or NULL */ - const extra_bits_t *extra_bits; /* extra bits for each code or NULL */ + const uint8_t *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; -struct global2 { +struct globals2 { ush heap[HEAP_SIZE]; /* heap used to build the Huffman trees */ int heap_len; /* number of elements in the heap */ @@ -953,31 +1056,21 @@ struct global2 { ulg opt_len; /* bit length of current block with optimal trees */ ulg static_len; /* bit length of current block with static trees */ - ulg compressed_len; /* total bit length of compressed file */ +// ulg compressed_len; /* total bit length of compressed file */ }; -#define G2ptr ((struct global2*)(ptr_to_globals)) +#define G2ptr ((struct globals2*)(ptr_to_globals)) #define G2 (*G2ptr) - /* =========================================================================== */ -static void gen_codes(ct_data * tree, int max_code); -static void build_tree(tree_desc * desc); -static void scan_tree(ct_data * tree, int max_code); -static void send_tree(ct_data * 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(ct_data * ltree, ct_data * dtree); - - #ifndef DEBUG /* Send a code of the given tree. c and tree must not have side effects */ # define SEND_CODE(c, tree) send_bits(tree[c].Code, tree[c].Len) #else # define SEND_CODE(c, tree) \ { \ - if (verbose > 1) bb_error_msg("\ncd %3d ",(c)); \ + if (verbose > 1) bb_error_msg("\ncd %3d ", (c)); \ send_bits(tree[c].Code, tree[c].Len); \ } #endif @@ -990,7 +1083,6 @@ static void compress_block(ct_data * ltree, ct_data * dtree); * The arguments must not have side effects. */ - /* =========================================================================== * Initialize a new block. */ @@ -1013,7 +1105,6 @@ static void init_block(void) G2.flag_bit = 1; } - /* =========================================================================== * Restore the heap property by moving down the tree starting at node k, * exchanging a node with the smallest of its two sons if necessary, stopping @@ -1051,7 +1142,6 @@ static void pqdownheap(ct_data * tree, int k) G2.heap[k] = v; } - /* =========================================================================== * Compute the optimal bit lengths for a tree and update the total bit length * for the current block. @@ -1065,7 +1155,7 @@ static void pqdownheap(ct_data * tree, int k) static void gen_bitlen(tree_desc * desc) { ct_data *tree = desc->dyn_tree; - const extra_bits_t *extra = desc->extra_bits; + const uint8_t *extra = desc->extra_bits; int base = desc->extra_base; int max_code = desc->max_code; int max_length = desc->max_length; @@ -1149,7 +1239,6 @@ static void gen_bitlen(tree_desc * desc) } } - /* =========================================================================== * Generate the codes for a given tree and bit counts (which need not be * optimal). @@ -1175,7 +1264,7 @@ static void gen_codes(ct_data * tree, int max_code) * must be all ones. */ Assert(code + G2.bl_count[MAX_BITS] - 1 == (1 << MAX_BITS) - 1, - "inconsistent bit counts"); + "inconsistent bit counts"); Tracev((stderr, "\ngen_codes: max_code %d ", max_code)); for (n = 0; n <= max_code; n++) { @@ -1188,12 +1277,11 @@ static void gen_codes(ct_data * tree, int max_code) Tracec(tree != G2.static_ltree, (stderr, "\nn %3d %c l %2d c %4x (%x) ", n, - (isgraph(n) ? n : ' '), len, tree[n].Code, + (n > ' ' ? n : ' '), len, tree[n].Code, next_code[len] - 1)); } } - /* =========================================================================== * Construct one Huffman tree and assigns the code bit strings and lengths. * Update the total bit length for the current block. @@ -1287,7 +1375,6 @@ static void build_tree(tree_desc * desc) /* and insert the new node in the heap */ G2.heap[SMALLEST] = node++; pqdownheap(tree, SMALLEST); - } while (G2.heap_len >= 2); G2.heap[--G2.heap_max] = G2.heap[SMALLEST]; @@ -1301,7 +1388,6 @@ static void build_tree(tree_desc * desc) gen_codes((ct_data *) tree, max_code); } - /* =========================================================================== * Scan a literal or distance tree to determine the frequencies of the codes * in the bit length tree. Updates opt_len to take into account the repeat @@ -1356,7 +1442,6 @@ static void scan_tree(ct_data * tree, int max_code) } } - /* =========================================================================== * Send a literal or distance tree in compressed form, using the codes in * bl_tree. @@ -1414,7 +1499,6 @@ static void send_tree(ct_data * tree, int max_code) } } - /* =========================================================================== * Construct the Huffman tree for the bit lengths and return the index in * bl_order of the last bit length code to send. @@ -1443,12 +1527,11 @@ static int build_bl_tree(void) } /* Update opt_len to include the bit length tree and counts */ G2.opt_len += 3 * (max_blindex + 1) + 5 + 5 + 4; - Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", G2.opt_len, G2.static_len)); + Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", (long)G2.opt_len, (long)G2.static_len)); return max_blindex; } - /* =========================================================================== * Send the header for a block using dynamic Huffman trees: the counts, the * lengths of the bit length codes, the literal tree and the distance tree. @@ -1469,16 +1552,15 @@ static void send_all_trees(int lcodes, int dcodes, int blcodes) Tracev((stderr, "\nbl code %2d ", bl_order[rank])); send_bits(G2.bl_tree[bl_order[rank]].Len, 3); } - Tracev((stderr, "\nbl tree: sent %ld", G1.bits_sent)); + Tracev((stderr, "\nbl tree: sent %ld", (long)G1.bits_sent)); send_tree((ct_data *) G2.dyn_ltree, lcodes - 1); /* send the literal tree */ - Tracev((stderr, "\nlit tree: sent %ld", G1.bits_sent)); + Tracev((stderr, "\nlit tree: sent %ld", (long)G1.bits_sent)); send_tree((ct_data *) G2.dyn_dtree, dcodes - 1); /* send the distance tree */ - Tracev((stderr, "\ndist tree: sent %ld", G1.bits_sent)); + Tracev((stderr, "\ndist tree: sent %ld", (long)G1.bits_sent)); } - /* =========================================================================== * Save the match info and tally the frequency counts. Return true if * the current block must be flushed. @@ -1523,9 +1605,10 @@ static int ct_tally(int dist, int lc) } out_length >>= 3; Trace((stderr, - "\nlast_lit %u, last_dist %u, in %ld, out ~%ld(%ld%%) ", - G2.last_lit, G2.last_dist, in_length, out_length, - 100L - out_length * 100L / in_length)); + "\nlast_lit %u, last_dist %u, in %ld, out ~%ld(%ld%%) ", + G2.last_lit, G2.last_dist, + (long)in_length, (long)out_length, + 100L - out_length * 100L / in_length)); if (G2.last_dist < G2.last_lit / 2 && out_length < in_length / 2) return 1; } @@ -1556,7 +1639,7 @@ static void compress_block(ct_data * ltree, ct_data * dtree) lc = G1.l_buf[lx++]; if ((flag & 1) == 0) { SEND_CODE(lc, ltree); /* send a literal byte */ - Tracecv(isgraph(lc), (stderr, " '%c' ", lc)); + Tracecv(lc > ' ', (stderr, " '%c' ", lc)); } else { /* Here, lc is the match length - MIN_MATCH */ code = G2.length_code[lc]; @@ -1584,13 +1667,12 @@ static void compress_block(ct_data * ltree, ct_data * dtree) SEND_CODE(END_BLOCK, ltree); } - /* =========================================================================== * Determine the best encoding for the current block: dynamic trees, static * trees or store, and output the encoded block to the zip file. This function * returns the total compressed length for the file so far. */ -static ulg flush_block(char *buf, ulg stored_len, int eof) +static void flush_block(char *buf, ulg stored_len, int eof) { ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ int max_blindex; /* index of last bit length code of non zero freq */ @@ -1599,10 +1681,10 @@ static ulg flush_block(char *buf, ulg stored_len, int eof) /* Construct the literal and distance trees */ build_tree(&G2.l_desc); - Tracev((stderr, "\nlit data: dyn %ld, stat %ld", G2.opt_len, G2.static_len)); + Tracev((stderr, "\nlit data: dyn %ld, stat %ld", (long)G2.opt_len, (long)G2.static_len)); build_tree(&G2.d_desc); - Tracev((stderr, "\ndist data: dyn %ld, stat %ld", G2.opt_len, G2.static_len)); + Tracev((stderr, "\ndist data: dyn %ld, stat %ld", (long)G2.opt_len, (long)G2.static_len)); /* At this point, opt_len and static_len are the total bit lengths of * the compressed block data, excluding the tree representations. */ @@ -1617,9 +1699,11 @@ static ulg flush_block(char *buf, ulg stored_len, int eof) static_lenb = (G2.static_len + 3 + 7) >> 3; Trace((stderr, - "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u dist %u ", - opt_lenb, G2.opt_len, static_lenb, G2.static_len, stored_len, - G2.last_lit, G2.last_dist)); + "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u dist %u ", + (unsigned long)opt_lenb, (unsigned long)G2.opt_len, + (unsigned long)static_lenb, (unsigned long)G2.static_len, + (unsigned long)stored_len, + G2.last_lit, G2.last_dist)); if (static_lenb <= opt_lenb) opt_lenb = static_lenb; @@ -1628,15 +1712,17 @@ static ulg flush_block(char *buf, ulg stored_len, int eof) * and if the zip file can be seeked (to rewrite the local header), * the whole file is transformed into a stored file: */ - if (stored_len <= opt_lenb && eof && G2.compressed_len == 0L && seekable()) { - /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */ - if (buf == NULL) - bb_error_msg("block vanished"); - - copy_block(buf, (unsigned) stored_len, 0); /* without header */ - G2.compressed_len = stored_len << 3; - - } else if (stored_len + 4 <= opt_lenb && buf != NULL) { +// seekable() is constant FALSE in busybox, and G2.compressed_len is disabled +// (this was the only user) +// if (stored_len <= opt_lenb && eof && G2.compressed_len == 0L && seekable()) { +// /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */ +// if (buf == NULL) +// bb_error_msg("block vanished"); +// +// G2.compressed_len = stored_len << 3; +// copy_block(buf, (unsigned) stored_len, 0); /* without header */ +// } else + if (stored_len + 4 <= opt_lenb && buf != 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 @@ -1645,45 +1731,43 @@ static ulg flush_block(char *buf, ulg stored_len, int eof) * transform a block into a stored block. */ send_bits((STORED_BLOCK << 1) + eof, 3); /* send block type */ - G2.compressed_len = (G2.compressed_len + 3 + 7) & ~7L; - G2.compressed_len += (stored_len + 4) << 3; - +// G2.compressed_len = ((G2.compressed_len + 3 + 7) & ~7L) +// + ((stored_len + 4) << 3); copy_block(buf, (unsigned) stored_len, 1); /* with header */ - - } else if (static_lenb == opt_lenb) { + } else + if (static_lenb == opt_lenb) { send_bits((STATIC_TREES << 1) + eof, 3); compress_block((ct_data *) G2.static_ltree, (ct_data *) G2.static_dtree); - G2.compressed_len += 3 + G2.static_len; +// G2.compressed_len += 3 + G2.static_len; } else { send_bits((DYN_TREES << 1) + eof, 3); send_all_trees(G2.l_desc.max_code + 1, G2.d_desc.max_code + 1, - max_blindex + 1); + max_blindex + 1); compress_block((ct_data *) G2.dyn_ltree, (ct_data *) G2.dyn_dtree); - G2.compressed_len += 3 + G2.opt_len; +// G2.compressed_len += 3 + G2.opt_len; } - Assert(G2.compressed_len == G1.bits_sent, "bad compressed size"); +// Assert(G2.compressed_len == G1.bits_sent, "bad compressed size"); init_block(); if (eof) { bi_windup(); - G2.compressed_len += 7; /* align on byte boundary */ +// G2.compressed_len += 7; /* align on byte boundary */ } - Tracev((stderr, "\ncomprlen %lu(%lu) ", G2.compressed_len >> 3, - G2.compressed_len - 7 * eof)); +// Tracev((stderr, "\ncomprlen %lu(%lu) ", +// (unsigned long)G2.compressed_len >> 3, +// (unsigned long)G2.compressed_len - 7 * eof)); - return G2.compressed_len >> 3; + return; /* was "return G2.compressed_len >> 3;" */ } - /* =========================================================================== * Update a hash value with the given input byte - * IN assertion: all calls to to UPDATE_HASH are made with consecutive + * IN assertion: all calls 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)<>= (BBUNPK_OPTSTRLEN IF_FEATURE_GZIP_DECOMPRESS(+ 2) + 1); /* drop cfkvq[dt]n bits */ + if (opt == 0) + opt = 1 << 6; /* default: 6 */ + opt = ffs(opt >> 4); /* Maps -1..-4 to [0], -5 to [1] ... -9 to [5] */ + max_chain_length = 1 << gzip_level_config[opt].chain_shift; + good_match = gzip_level_config[opt].good; + max_lazy_match = gzip_level_config[opt].lazy2 * 2; + nice_match = gzip_level_config[opt].nice2 * 2; +#endif + option_mask32 &= BBUNPK_OPTSTRMASK; /* retain only -cfkvq */ /* Allocate all global buffers (for DYN_ALLOC option) */ ALLOC(uch, G1.l_buf, INBUFSIZ); @@ -2081,8 +2238,9 @@ int gzip_main(int argc, char **argv) ALLOC(uch, G1.window, 2L * WSIZE); ALLOC(ush, G1.prev, 1L << BITS); - /* Initialise the CRC32 table */ - G1.crc_32_tab = crc32_filltable(0); + /* Initialize the CRC32 table */ + global_crc32_new_table_le(); - return bbunpack(argv, make_new_name_gzip, pack_gzip); + argv += optind; + return bbunpack(argv, pack_gzip, append_ext, "gz"); }