source: branches/3.2/mindi-busybox/archival/gzip.c @ 3232

Last change on this file since 3232 was 3232, checked in by bruno, 6 years ago
  • Update mindi-busybox to 1.21.1
File size: 65.0 KB
Line 
1/* vi: set sw=4 ts=4: */
2/*
3 * Gzip implementation for busybox
4 *
5 * Based on GNU gzip Copyright (C) 1992-1993 Jean-loup Gailly.
6 *
7 * Originally adjusted for busybox by Charles P. Wright <cpw@unix.asb.com>
8 * "this is a stripped down version of gzip I put into busybox, it does
9 * only standard in to standard out with -9 compression.  It also requires
10 * the zcat module for some important functions."
11 *
12 * Adjusted further by Erik Andersen <andersen@codepoet.org> to support
13 * files as well as stdin/stdout, and to generally behave itself wrt
14 * command line handling.
15 *
16 * Licensed under GPLv2 or later, see file LICENSE in this source tree.
17 */
18
19/* big objects in bss:
20 * 00000020 b bl_count
21 * 00000074 b base_length
22 * 00000078 b base_dist
23 * 00000078 b static_dtree
24 * 0000009c b bl_tree
25 * 000000f4 b dyn_dtree
26 * 00000100 b length_code
27 * 00000200 b dist_code
28 * 0000023d b depth
29 * 00000400 b flag_buf
30 * 0000047a b heap
31 * 00000480 b static_ltree
32 * 000008f4 b dyn_ltree
33 */
34
35/* TODO: full support for -v for DESKTOP
36 * "/usr/bin/gzip -v a bogus aa" should say:
37a:       85.1% -- replaced with a.gz
38gzip: bogus: No such file or directory
39aa:      85.1% -- replaced with aa.gz
40*/
41
42//usage:#define gzip_trivial_usage
43//usage:       "[-cfd] [FILE]..."
44//usage:#define gzip_full_usage "\n\n"
45//usage:       "Compress FILEs (or stdin)\n"
46//usage:     "\n    -d  Decompress"
47//usage:     "\n    -c  Write to stdout"
48//usage:     "\n    -f  Force"
49//usage:
50//usage:#define gzip_example_usage
51//usage:       "$ ls -la /tmp/busybox*\n"
52//usage:       "-rw-rw-r--    1 andersen andersen  1761280 Apr 14 17:47 /tmp/busybox.tar\n"
53//usage:       "$ gzip /tmp/busybox.tar\n"
54//usage:       "$ ls -la /tmp/busybox*\n"
55//usage:       "-rw-rw-r--    1 andersen andersen   554058 Apr 14 17:49 /tmp/busybox.tar.gz\n"
56
57#include "libbb.h"
58#include "bb_archive.h"
59
60
61/* ===========================================================================
62 */
63//#define DEBUG 1
64/* Diagnostic functions */
65#ifdef DEBUG
66#  define Assert(cond,msg) { if (!(cond)) bb_error_msg(msg); }
67#  define Trace(x) fprintf x
68#  define Tracev(x) {if (verbose) fprintf x; }
69#  define Tracevv(x) {if (verbose > 1) fprintf x; }
70#  define Tracec(c,x) {if (verbose && (c)) fprintf x; }
71#  define Tracecv(c,x) {if (verbose > 1 && (c)) fprintf x; }
72#else
73#  define Assert(cond,msg)
74#  define Trace(x)
75#  define Tracev(x)
76#  define Tracevv(x)
77#  define Tracec(c,x)
78#  define Tracecv(c,x)
79#endif
80
81
82/* ===========================================================================
83 */
84#if   CONFIG_GZIP_FAST == 0
85# define SMALL_MEM
86#elif CONFIG_GZIP_FAST == 1
87# define MEDIUM_MEM
88#elif CONFIG_GZIP_FAST == 2
89# define BIG_MEM
90#else
91# error "Invalid CONFIG_GZIP_FAST value"
92#endif
93
94#ifndef INBUFSIZ
95#  ifdef SMALL_MEM
96#    define INBUFSIZ  0x2000    /* input buffer size */
97#  else
98#    define INBUFSIZ  0x8000    /* input buffer size */
99#  endif
100#endif
101
102#ifndef OUTBUFSIZ
103#  ifdef SMALL_MEM
104#    define OUTBUFSIZ   8192    /* output buffer size */
105#  else
106#    define OUTBUFSIZ  16384    /* output buffer size */
107#  endif
108#endif
109
110#ifndef DIST_BUFSIZE
111#  ifdef SMALL_MEM
112#    define DIST_BUFSIZE 0x2000 /* buffer for distances, see trees.c */
113#  else
114#    define DIST_BUFSIZE 0x8000 /* buffer for distances, see trees.c */
115#  endif
116#endif
117
118/* gzip flag byte */
119#define ASCII_FLAG   0x01   /* bit 0 set: file probably ascii text */
120#define CONTINUATION 0x02   /* bit 1 set: continuation of multi-part gzip file */
121#define EXTRA_FIELD  0x04   /* bit 2 set: extra field present */
122#define ORIG_NAME    0x08   /* bit 3 set: original file name present */
123#define COMMENT      0x10   /* bit 4 set: file comment present */
124#define RESERVED     0xC0   /* bit 6,7:   reserved */
125
126/* internal file attribute */
127#define UNKNOWN 0xffff
128#define BINARY  0
129#define ASCII   1
130
131#ifndef WSIZE
132#  define WSIZE 0x8000  /* window size--must be a power of two, and */
133#endif                  /*  at least 32K for zip's deflate method */
134
135#define MIN_MATCH  3
136#define MAX_MATCH  258
137/* The minimum and maximum match lengths */
138
139#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
140/* Minimum amount of lookahead, except at the end of the input file.
141 * See deflate.c for comments about the MIN_MATCH+1.
142 */
143
144#define MAX_DIST  (WSIZE-MIN_LOOKAHEAD)
145/* In order to simplify the code, particularly on 16 bit machines, match
146 * distances are limited to MAX_DIST instead of WSIZE.
147 */
148
149#ifndef MAX_PATH_LEN
150#  define MAX_PATH_LEN   1024   /* max pathname length */
151#endif
152
153#define seekable()    0 /* force sequential output */
154#define translate_eol 0 /* no option -a yet */
155
156#ifndef BITS
157#  define BITS 16
158#endif
159#define INIT_BITS 9     /* Initial number of bits per code */
160
161#define BIT_MASK    0x1f    /* Mask for 'number of compression bits' */
162/* Mask 0x20 is reserved to mean a fourth header byte, and 0x40 is free.
163 * It's a pity that old uncompress does not check bit 0x20. That makes
164 * extension of the format actually undesirable because old compress
165 * would just crash on the new format instead of giving a meaningful
166 * error message. It does check the number of bits, but it's more
167 * helpful to say "unsupported format, get a new version" than
168 * "can only handle 16 bits".
169 */
170
171#ifdef MAX_EXT_CHARS
172#  define MAX_SUFFIX  MAX_EXT_CHARS
173#else
174#  define MAX_SUFFIX  30
175#endif
176
177
178/* ===========================================================================
179 * Compile with MEDIUM_MEM to reduce the memory requirements or
180 * with SMALL_MEM to use as little memory as possible. Use BIG_MEM if the
181 * entire input file can be held in memory (not possible on 16 bit systems).
182 * Warning: defining these symbols affects HASH_BITS (see below) and thus
183 * affects the compression ratio. The compressed output
184 * is still correct, and might even be smaller in some cases.
185 */
186
187#ifdef SMALL_MEM
188#   define HASH_BITS  13    /* Number of bits used to hash strings */
189#endif
190#ifdef MEDIUM_MEM
191#   define HASH_BITS  14
192#endif
193#ifndef HASH_BITS
194#   define HASH_BITS  15
195   /* For portability to 16 bit machines, do not use values above 15. */
196#endif
197
198#define HASH_SIZE (unsigned)(1<<HASH_BITS)
199#define HASH_MASK (HASH_SIZE-1)
200#define WMASK     (WSIZE-1)
201/* HASH_SIZE and WSIZE must be powers of two */
202#ifndef TOO_FAR
203#  define TOO_FAR 4096
204#endif
205/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
206
207
208/* ===========================================================================
209 * These types are not really 'char', 'short' and 'long'
210 */
211typedef uint8_t uch;
212typedef uint16_t ush;
213typedef uint32_t ulg;
214typedef int32_t lng;
215
216typedef ush Pos;
217typedef unsigned IPos;
218/* A Pos is an index in the character window. We use short instead of int to
219 * save space in the various tables. IPos is used only for parameter passing.
220 */
221
222enum {
223    WINDOW_SIZE = 2 * WSIZE,
224/* window size, 2*WSIZE except for MMAP or BIG_MEM, where it is the
225 * input file length plus MIN_LOOKAHEAD.
226 */
227
228    max_chain_length = 4096,
229/* To speed up deflation, hash chains are never searched beyond this length.
230 * A higher limit improves compression ratio but degrades the speed.
231 */
232
233    max_lazy_match = 258,
234/* Attempt to find a better match only when the current match is strictly
235 * smaller than this value. This mechanism is used only for compression
236 * levels >= 4.
237 */
238
239    max_insert_length = max_lazy_match,
240/* Insert new strings in the hash table only if the match length
241 * is not greater than this length. This saves time but degrades compression.
242 * max_insert_length is used only for compression levels <= 3.
243 */
244
245    good_match = 32,
246/* Use a faster search when the previous match is longer than this */
247
248/* Values for max_lazy_match, good_match and max_chain_length, depending on
249 * the desired pack level (0..9). The values given below have been tuned to
250 * exclude worst case performance for pathological files. Better values may be
251 * found for specific files.
252 */
253
254    nice_match = 258,   /* Stop searching when current match exceeds this */
255/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
256 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
257 * meaning.
258 */
259};
260
261
262struct globals {
263
264    lng block_start;
265
266/* window position at the beginning of the current output block. Gets
267 * negative when the window is moved backwards.
268 */
269    unsigned ins_h; /* hash index of string to be inserted */
270
271#define H_SHIFT  ((HASH_BITS+MIN_MATCH-1) / MIN_MATCH)
272/* Number of bits by which ins_h and del_h must be shifted at each
273 * input step. It must be such that after MIN_MATCH steps, the oldest
274 * byte no longer takes part in the hash key, that is:
275 * H_SHIFT * MIN_MATCH >= HASH_BITS
276 */
277
278    unsigned prev_length;
279
280/* Length of the best match at previous step. Matches not greater than this
281 * are discarded. This is used in the lazy match evaluation.
282 */
283
284    unsigned strstart;  /* start of string to insert */
285    unsigned match_start;   /* start of matching string */
286    unsigned lookahead; /* number of valid bytes ahead in window */
287
288/* ===========================================================================
289 */
290#define DECLARE(type, array, size) \
291    type * array
292#define ALLOC(type, array, size) \
293    array = xzalloc((size_t)(((size)+1L)/2) * 2*sizeof(type))
294#define FREE(array) \
295    do { free(array); array = NULL; } while (0)
296
297    /* global buffers */
298
299    /* buffer for literals or lengths */
300    /* DECLARE(uch, l_buf, LIT_BUFSIZE); */
301    DECLARE(uch, l_buf, INBUFSIZ);
302
303    DECLARE(ush, d_buf, DIST_BUFSIZE);
304    DECLARE(uch, outbuf, OUTBUFSIZ);
305
306/* Sliding window. Input bytes are read into the second half of the window,
307 * and move to the first half later to keep a dictionary of at least WSIZE
308 * bytes. With this organization, matches are limited to a distance of
309 * WSIZE-MAX_MATCH bytes, but this ensures that IO is always
310 * performed with a length multiple of the block size. Also, it limits
311 * the window size to 64K, which is quite useful on MSDOS.
312 * To do: limit the window size to WSIZE+BSZ if SMALL_MEM (the code would
313 * be less efficient).
314 */
315    DECLARE(uch, window, 2L * WSIZE);
316
317/* Link to older string with same hash index. To limit the size of this
318 * array to 64K, this link is maintained only for the last 32K strings.
319 * An index in this array is thus a window index modulo 32K.
320 */
321    /* DECLARE(Pos, prev, WSIZE); */
322    DECLARE(ush, prev, 1L << BITS);
323
324/* Heads of the hash chains or 0. */
325    /* DECLARE(Pos, head, 1<<HASH_BITS); */
326#define head (G1.prev + WSIZE) /* hash head (see deflate.c) */
327
328/* number of input bytes */
329    ulg isize;      /* only 32 bits stored in .gz file */
330
331/* bbox always use stdin/stdout */
332#define ifd STDIN_FILENO    /* input file descriptor */
333#define ofd STDOUT_FILENO   /* output file descriptor */
334
335#ifdef DEBUG
336    unsigned insize;    /* valid bytes in l_buf */
337#endif
338    unsigned outcnt;    /* bytes in output buffer */
339
340    smallint eofile;    /* flag set at end of input file */
341
342/* ===========================================================================
343 * Local data used by the "bit string" routines.
344 */
345
346    unsigned short bi_buf;
347
348/* Output buffer. bits are inserted starting at the bottom (least significant
349 * bits).
350 */
351
352#undef BUF_SIZE
353#define BUF_SIZE (8 * sizeof(G1.bi_buf))
354/* Number of bits used within bi_buf. (bi_buf might be implemented on
355 * more than 16 bits on some systems.)
356 */
357
358    int bi_valid;
359
360/* Current input function. Set to mem_read for in-memory compression */
361
362#ifdef DEBUG
363    ulg bits_sent;          /* bit length of the compressed data */
364#endif
365
366    /*uint32_t *crc_32_tab;*/
367    uint32_t crc;   /* shift register contents */
368};
369
370#define G1 (*(ptr_to_globals - 1))
371
372
373/* ===========================================================================
374 * Write the output buffer outbuf[0..outcnt-1] and update bytes_out.
375 * (used for the compressed data only)
376 */
377static void flush_outbuf(void)
378{
379    if (G1.outcnt == 0)
380        return;
381
382    xwrite(ofd, (char *) G1.outbuf, G1.outcnt);
383    G1.outcnt = 0;
384}
385
386
387/* ===========================================================================
388 */
389/* put_8bit is used for the compressed output */
390#define put_8bit(c) \
391do { \
392    G1.outbuf[G1.outcnt++] = (c); \
393    if (G1.outcnt == OUTBUFSIZ) flush_outbuf(); \
394} while (0)
395
396/* Output a 16 bit value, lsb first */
397static void put_16bit(ush w)
398{
399    if (G1.outcnt < OUTBUFSIZ - 2) {
400        G1.outbuf[G1.outcnt++] = w;
401        G1.outbuf[G1.outcnt++] = w >> 8;
402    } else {
403        put_8bit(w);
404        put_8bit(w >> 8);
405    }
406}
407
408static void put_32bit(ulg n)
409{
410    put_16bit(n);
411    put_16bit(n >> 16);
412}
413
414/* ===========================================================================
415 * Run a set of bytes through the crc shift register.  If s is a NULL
416 * pointer, then initialize the crc shift register contents instead.
417 * Return the current crc in either case.
418 */
419static void updcrc(uch * s, unsigned n)
420{
421    G1.crc = crc32_block_endian0(G1.crc, s, n, global_crc32_table /*G1.crc_32_tab*/);
422}
423
424
425/* ===========================================================================
426 * Read a new buffer from the current input file, perform end-of-line
427 * translation, and update the crc and input file size.
428 * IN assertion: size >= 2 (for end-of-line translation)
429 */
430static unsigned file_read(void *buf, unsigned size)
431{
432    unsigned len;
433
434    Assert(G1.insize == 0, "l_buf not empty");
435
436    len = safe_read(ifd, buf, size);
437    if (len == (unsigned)(-1) || len == 0)
438        return len;
439
440    updcrc(buf, len);
441    G1.isize += len;
442    return len;
443}
444
445
446/* ===========================================================================
447 * Send a value on a given number of bits.
448 * IN assertion: length <= 16 and value fits in length bits.
449 */
450static void send_bits(int value, int length)
451{
452#ifdef DEBUG
453    Tracev((stderr, " l %2d v %4x ", length, value));
454    Assert(length > 0 && length <= 15, "invalid length");
455    G1.bits_sent += length;
456#endif
457    /* If not enough room in bi_buf, use (valid) bits from bi_buf and
458     * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
459     * unused bits in value.
460     */
461    if (G1.bi_valid > (int) BUF_SIZE - length) {
462        G1.bi_buf |= (value << G1.bi_valid);
463        put_16bit(G1.bi_buf);
464        G1.bi_buf = (ush) value >> (BUF_SIZE - G1.bi_valid);
465        G1.bi_valid += length - BUF_SIZE;
466    } else {
467        G1.bi_buf |= value << G1.bi_valid;
468        G1.bi_valid += length;
469    }
470}
471
472
473/* ===========================================================================
474 * Reverse the first len bits of a code, using straightforward code (a faster
475 * method would use a table)
476 * IN assertion: 1 <= len <= 15
477 */
478static unsigned bi_reverse(unsigned code, int len)
479{
480    unsigned res = 0;
481
482    while (1) {
483        res |= code & 1;
484        if (--len <= 0) return res;
485        code >>= 1;
486        res <<= 1;
487    }
488}
489
490
491/* ===========================================================================
492 * Write out any remaining bits in an incomplete byte.
493 */
494static void bi_windup(void)
495{
496    if (G1.bi_valid > 8) {
497        put_16bit(G1.bi_buf);
498    } else if (G1.bi_valid > 0) {
499        put_8bit(G1.bi_buf);
500    }
501    G1.bi_buf = 0;
502    G1.bi_valid = 0;
503#ifdef DEBUG
504    G1.bits_sent = (G1.bits_sent + 7) & ~7;
505#endif
506}
507
508
509/* ===========================================================================
510 * Copy a stored block to the zip file, storing first the length and its
511 * one's complement if requested.
512 */
513static void copy_block(char *buf, unsigned len, int header)
514{
515    bi_windup();        /* align on byte boundary */
516
517    if (header) {
518        put_16bit(len);
519        put_16bit(~len);
520#ifdef DEBUG
521        G1.bits_sent += 2 * 16;
522#endif
523    }
524#ifdef DEBUG
525    G1.bits_sent += (ulg) len << 3;
526#endif
527    while (len--) {
528        put_8bit(*buf++);
529    }
530}
531
532
533/* ===========================================================================
534 * Fill the window when the lookahead becomes insufficient.
535 * Updates strstart and lookahead, and sets eofile if end of input file.
536 * IN assertion: lookahead < MIN_LOOKAHEAD && strstart + lookahead > 0
537 * OUT assertions: at least one byte has been read, or eofile is set;
538 *    file reads are performed for at least two bytes (required for the
539 *    translate_eol option).
540 */
541static void fill_window(void)
542{
543    unsigned n, m;
544    unsigned more = WINDOW_SIZE - G1.lookahead - G1.strstart;
545    /* Amount of free space at the end of the window. */
546
547    /* If the window is almost full and there is insufficient lookahead,
548     * move the upper half to the lower one to make room in the upper half.
549     */
550    if (more == (unsigned) -1) {
551        /* Very unlikely, but possible on 16 bit machine if strstart == 0
552         * and lookahead == 1 (input done one byte at time)
553         */
554        more--;
555    } else if (G1.strstart >= WSIZE + MAX_DIST) {
556        /* By the IN assertion, the window is not empty so we can't confuse
557         * more == 0 with more == 64K on a 16 bit machine.
558         */
559        Assert(WINDOW_SIZE == 2 * WSIZE, "no sliding with BIG_MEM");
560
561        memcpy(G1.window, G1.window + WSIZE, WSIZE);
562        G1.match_start -= WSIZE;
563        G1.strstart -= WSIZE;   /* we now have strstart >= MAX_DIST: */
564
565        G1.block_start -= WSIZE;
566
567        for (n = 0; n < HASH_SIZE; n++) {
568            m = head[n];
569            head[n] = (Pos) (m >= WSIZE ? m - WSIZE : 0);
570        }
571        for (n = 0; n < WSIZE; n++) {
572            m = G1.prev[n];
573            G1.prev[n] = (Pos) (m >= WSIZE ? m - WSIZE : 0);
574            /* If n is not on any hash chain, prev[n] is garbage but
575             * its value will never be used.
576             */
577        }
578        more += WSIZE;
579    }
580    /* At this point, more >= 2 */
581    if (!G1.eofile) {
582        n = file_read(G1.window + G1.strstart + G1.lookahead, more);
583        if (n == 0 || n == (unsigned) -1) {
584            G1.eofile = 1;
585        } else {
586            G1.lookahead += n;
587        }
588    }
589}
590
591
592/* ===========================================================================
593 * Set match_start to the longest match starting at the given string and
594 * return its length. Matches shorter or equal to prev_length are discarded,
595 * in which case the result is equal to prev_length and match_start is
596 * garbage.
597 * IN assertions: cur_match is the head of the hash chain for the current
598 *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
599 */
600
601/* For MSDOS, OS/2 and 386 Unix, an optimized version is in match.asm or
602 * match.s. The code is functionally equivalent, so you can use the C version
603 * if desired.
604 */
605static int longest_match(IPos cur_match)
606{
607    unsigned chain_length = max_chain_length;   /* max hash chain length */
608    uch *scan = G1.window + G1.strstart;    /* current string */
609    uch *match; /* matched string */
610    int len;    /* length of current match */
611    int best_len = G1.prev_length;  /* best match length so far */
612    IPos limit = G1.strstart > (IPos) MAX_DIST ? G1.strstart - (IPos) MAX_DIST : 0;
613    /* Stop when cur_match becomes <= limit. To simplify the code,
614     * we prevent matches with the string of window index 0.
615     */
616
617/* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
618 * It is easy to get rid of this optimization if necessary.
619 */
620#if HASH_BITS < 8 || MAX_MATCH != 258
621#  error Code too clever
622#endif
623    uch *strend = G1.window + G1.strstart + MAX_MATCH;
624    uch scan_end1 = scan[best_len - 1];
625    uch scan_end = scan[best_len];
626
627    /* Do not waste too much time if we already have a good match: */
628    if (G1.prev_length >= good_match) {
629        chain_length >>= 2;
630    }
631    Assert(G1.strstart <= WINDOW_SIZE - MIN_LOOKAHEAD, "insufficient lookahead");
632
633    do {
634        Assert(cur_match < G1.strstart, "no future");
635        match = G1.window + cur_match;
636
637        /* Skip to next match if the match length cannot increase
638         * or if the match length is less than 2:
639         */
640        if (match[best_len] != scan_end
641         || match[best_len - 1] != scan_end1
642         || *match != *scan || *++match != scan[1]
643        ) {
644            continue;
645        }
646
647        /* The check at best_len-1 can be removed because it will be made
648         * again later. (This heuristic is not always a win.)
649         * It is not necessary to compare scan[2] and match[2] since they
650         * are always equal when the other bytes match, given that
651         * the hash keys are equal and that HASH_BITS >= 8.
652         */
653        scan += 2, match++;
654
655        /* We check for insufficient lookahead only every 8th comparison;
656         * the 256th check will be made at strstart+258.
657         */
658        do {
659        } while (*++scan == *++match && *++scan == *++match &&
660                 *++scan == *++match && *++scan == *++match &&
661                 *++scan == *++match && *++scan == *++match &&
662                 *++scan == *++match && *++scan == *++match && scan < strend);
663
664        len = MAX_MATCH - (int) (strend - scan);
665        scan = strend - MAX_MATCH;
666
667        if (len > best_len) {
668            G1.match_start = cur_match;
669            best_len = len;
670            if (len >= nice_match)
671                break;
672            scan_end1 = scan[best_len - 1];
673            scan_end = scan[best_len];
674        }
675    } while ((cur_match = G1.prev[cur_match & WMASK]) > limit
676             && --chain_length != 0);
677
678    return best_len;
679}
680
681
682#ifdef DEBUG
683/* ===========================================================================
684 * Check that the match at match_start is indeed a match.
685 */
686static void check_match(IPos start, IPos match, int length)
687{
688    /* check that the match is indeed a match */
689    if (memcmp(G1.window + match, G1.window + start, length) != 0) {
690        bb_error_msg(" start %d, match %d, length %d", start, match, length);
691        bb_error_msg("invalid match");
692    }
693    if (verbose > 1) {
694        bb_error_msg("\\[%d,%d]", start - match, length);
695        do {
696            bb_putchar_stderr(G1.window[start++]);
697        } while (--length != 0);
698    }
699}
700#else
701#  define check_match(start, match, length) ((void)0)
702#endif
703
704
705/* trees.c -- output deflated data using Huffman coding
706 * Copyright (C) 1992-1993 Jean-loup Gailly
707 * This is free software; you can redistribute it and/or modify it under the
708 * terms of the GNU General Public License, see the file COPYING.
709 */
710
711/*  PURPOSE
712 *      Encode various sets of source values using variable-length
713 *      binary code trees.
714 *
715 *  DISCUSSION
716 *      The PKZIP "deflation" process uses several Huffman trees. The more
717 *      common source values are represented by shorter bit sequences.
718 *
719 *      Each code tree is stored in the ZIP file in a compressed form
720 *      which is itself a Huffman encoding of the lengths of
721 *      all the code strings (in ascending order by source values).
722 *      The actual code strings are reconstructed from the lengths in
723 *      the UNZIP process, as described in the "application note"
724 *      (APPNOTE.TXT) distributed as part of PKWARE's PKZIP program.
725 *
726 *  REFERENCES
727 *      Lynch, Thomas J.
728 *          Data Compression:  Techniques and Applications, pp. 53-55.
729 *          Lifetime Learning Publications, 1985.  ISBN 0-534-03418-7.
730 *
731 *      Storer, James A.
732 *          Data Compression:  Methods and Theory, pp. 49-50.
733 *          Computer Science Press, 1988.  ISBN 0-7167-8156-5.
734 *
735 *      Sedgewick, R.
736 *          Algorithms, p290.
737 *          Addison-Wesley, 1983. ISBN 0-201-06672-6.
738 *
739 *  INTERFACE
740 *      void ct_init()
741 *          Allocate the match buffer, initialize the various tables [and save
742 *          the location of the internal file attribute (ascii/binary) and
743 *          method (DEFLATE/STORE) -- deleted in bbox]
744 *
745 *      void ct_tally(int dist, int lc);
746 *          Save the match info and tally the frequency counts.
747 *
748 *      ulg flush_block(char *buf, ulg stored_len, int eof)
749 *          Determine the best encoding for the current block: dynamic trees,
750 *          static trees or store, and output the encoded block to the zip
751 *          file. Returns the total compressed length for the file so far.
752 */
753
754#define MAX_BITS 15
755/* All codes must not exceed MAX_BITS bits */
756
757#define MAX_BL_BITS 7
758/* Bit length codes must not exceed MAX_BL_BITS bits */
759
760#define LENGTH_CODES 29
761/* number of length codes, not counting the special END_BLOCK code */
762
763#define LITERALS  256
764/* number of literal bytes 0..255 */
765
766#define END_BLOCK 256
767/* end of block literal code */
768
769#define L_CODES (LITERALS+1+LENGTH_CODES)
770/* number of Literal or Length codes, including the END_BLOCK code */
771
772#define D_CODES   30
773/* number of distance codes */
774
775#define BL_CODES  19
776/* number of codes used to transfer the bit lengths */
777
778/* extra bits for each length code */
779static const uint8_t extra_lbits[LENGTH_CODES] ALIGN1 = {
780    0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4,
781    4, 4, 5, 5, 5, 5, 0
782};
783
784/* extra bits for each distance code */
785static const uint8_t extra_dbits[D_CODES] ALIGN1 = {
786    0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9,
787    10, 10, 11, 11, 12, 12, 13, 13
788};
789
790/* extra bits for each bit length code */
791static const uint8_t extra_blbits[BL_CODES] ALIGN1 = {
792    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7 };
793
794/* number of codes at each bit length for an optimal tree */
795static const uint8_t bl_order[BL_CODES] ALIGN1 = {
796    16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
797
798#define STORED_BLOCK 0
799#define STATIC_TREES 1
800#define DYN_TREES    2
801/* The three kinds of block type */
802
803#ifndef LIT_BUFSIZE
804#  ifdef SMALL_MEM
805#    define LIT_BUFSIZE  0x2000
806#  else
807#  ifdef MEDIUM_MEM
808#    define LIT_BUFSIZE  0x4000
809#  else
810#    define LIT_BUFSIZE  0x8000
811#  endif
812#  endif
813#endif
814#ifndef DIST_BUFSIZE
815#  define DIST_BUFSIZE  LIT_BUFSIZE
816#endif
817/* Sizes of match buffers for literals/lengths and distances.  There are
818 * 4 reasons for limiting LIT_BUFSIZE to 64K:
819 *   - frequencies can be kept in 16 bit counters
820 *   - if compression is not successful for the first block, all input data is
821 *     still in the window so we can still emit a stored block even when input
822 *     comes from standard input.  (This can also be done for all blocks if
823 *     LIT_BUFSIZE is not greater than 32K.)
824 *   - if compression is not successful for a file smaller than 64K, we can
825 *     even emit a stored file instead of a stored block (saving 5 bytes).
826 *   - creating new Huffman trees less frequently may not provide fast
827 *     adaptation to changes in the input data statistics. (Take for
828 *     example a binary file with poorly compressible code followed by
829 *     a highly compressible string table.) Smaller buffer sizes give
830 *     fast adaptation but have of course the overhead of transmitting trees
831 *     more frequently.
832 *   - I can't count above 4
833 * The current code is general and allows DIST_BUFSIZE < LIT_BUFSIZE (to save
834 * memory at the expense of compression). Some optimizations would be possible
835 * if we rely on DIST_BUFSIZE == LIT_BUFSIZE.
836 */
837#define REP_3_6      16
838/* repeat previous bit length 3-6 times (2 bits of repeat count) */
839#define REPZ_3_10    17
840/* repeat a zero length 3-10 times  (3 bits of repeat count) */
841#define REPZ_11_138  18
842/* repeat a zero length 11-138 times  (7 bits of repeat count) */
843
844/* ===========================================================================
845*/
846/* Data structure describing a single value and its code string. */
847typedef struct ct_data {
848    union {
849        ush freq;       /* frequency count */
850        ush code;       /* bit string */
851    } fc;
852    union {
853        ush dad;        /* father node in Huffman tree */
854        ush len;        /* length of bit string */
855    } dl;
856} ct_data;
857
858#define Freq fc.freq
859#define Code fc.code
860#define Dad  dl.dad
861#define Len  dl.len
862
863#define HEAP_SIZE (2*L_CODES + 1)
864/* maximum heap size */
865
866typedef struct tree_desc {
867    ct_data *dyn_tree;  /* the dynamic tree */
868    ct_data *static_tree;   /* corresponding static tree or NULL */
869    const uint8_t *extra_bits;  /* extra bits for each code or NULL */
870    int extra_base;     /* base index for extra_bits */
871    int elems;          /* max number of elements in the tree */
872    int max_length;     /* max bit length for the codes */
873    int max_code;       /* largest code with non zero frequency */
874} tree_desc;
875
876struct globals2 {
877
878    ush heap[HEAP_SIZE];     /* heap used to build the Huffman trees */
879    int heap_len;            /* number of elements in the heap */
880    int heap_max;            /* element of largest frequency */
881
882/* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
883 * The same heap array is used to build all trees.
884 */
885
886    ct_data dyn_ltree[HEAP_SIZE];   /* literal and length tree */
887    ct_data dyn_dtree[2 * D_CODES + 1]; /* distance tree */
888
889    ct_data static_ltree[L_CODES + 2];
890
891/* The static literal tree. Since the bit lengths are imposed, there is no
892 * need for the L_CODES extra codes used during heap construction. However
893 * The codes 286 and 287 are needed to build a canonical tree (see ct_init
894 * below).
895 */
896
897    ct_data static_dtree[D_CODES];
898
899/* The static distance tree. (Actually a trivial tree since all codes use
900 * 5 bits.)
901 */
902
903    ct_data bl_tree[2 * BL_CODES + 1];
904
905/* Huffman tree for the bit lengths */
906
907    tree_desc l_desc;
908    tree_desc d_desc;
909    tree_desc bl_desc;
910
911    ush bl_count[MAX_BITS + 1];
912
913/* The lengths of the bit length codes are sent in order of decreasing
914 * probability, to avoid transmitting the lengths for unused bit length codes.
915 */
916
917    uch depth[2 * L_CODES + 1];
918
919/* Depth of each subtree used as tie breaker for trees of equal frequency */
920
921    uch length_code[MAX_MATCH - MIN_MATCH + 1];
922
923/* length code for each normalized match length (0 == MIN_MATCH) */
924
925    uch dist_code[512];
926
927/* distance codes. The first 256 values correspond to the distances
928 * 3 .. 258, the last 256 values correspond to the top 8 bits of
929 * the 15 bit distances.
930 */
931
932    int base_length[LENGTH_CODES];
933
934/* First normalized length for each code (0 = MIN_MATCH) */
935
936    int base_dist[D_CODES];
937
938/* First normalized distance for each code (0 = distance of 1) */
939
940    uch flag_buf[LIT_BUFSIZE / 8];
941
942/* flag_buf is a bit array distinguishing literals from lengths in
943 * l_buf, thus indicating the presence or absence of a distance.
944 */
945
946    unsigned last_lit;       /* running index in l_buf */
947    unsigned last_dist;      /* running index in d_buf */
948    unsigned last_flags;     /* running index in flag_buf */
949    uch flags;               /* current flags not yet saved in flag_buf */
950    uch flag_bit;            /* current bit used in flags */
951
952/* bits are filled in flags starting at bit 0 (least significant).
953 * Note: these flags are overkill in the current code since we don't
954 * take advantage of DIST_BUFSIZE == LIT_BUFSIZE.
955 */
956
957    ulg opt_len;             /* bit length of current block with optimal trees */
958    ulg static_len;          /* bit length of current block with static trees */
959
960    ulg compressed_len;      /* total bit length of compressed file */
961};
962
963#define G2ptr ((struct globals2*)(ptr_to_globals))
964#define G2 (*G2ptr)
965
966
967/* ===========================================================================
968 */
969static void gen_codes(ct_data * tree, int max_code);
970static void build_tree(tree_desc * desc);
971static void scan_tree(ct_data * tree, int max_code);
972static void send_tree(ct_data * tree, int max_code);
973static int build_bl_tree(void);
974static void send_all_trees(int lcodes, int dcodes, int blcodes);
975static void compress_block(ct_data * ltree, ct_data * dtree);
976
977
978#ifndef DEBUG
979/* Send a code of the given tree. c and tree must not have side effects */
980#  define SEND_CODE(c, tree) send_bits(tree[c].Code, tree[c].Len)
981#else
982#  define SEND_CODE(c, tree) \
983{ \
984    if (verbose > 1) bb_error_msg("\ncd %3d ", (c)); \
985    send_bits(tree[c].Code, tree[c].Len); \
986}
987#endif
988
989#define D_CODE(dist) \
990    ((dist) < 256 ? G2.dist_code[dist] : G2.dist_code[256 + ((dist)>>7)])
991/* Mapping from a distance to a distance code. dist is the distance - 1 and
992 * must not have side effects. dist_code[256] and dist_code[257] are never
993 * used.
994 * The arguments must not have side effects.
995 */
996
997
998/* ===========================================================================
999 * Initialize a new block.
1000 */
1001static void init_block(void)
1002{
1003    int n; /* iterates over tree elements */
1004
1005    /* Initialize the trees. */
1006    for (n = 0; n < L_CODES; n++)
1007        G2.dyn_ltree[n].Freq = 0;
1008    for (n = 0; n < D_CODES; n++)
1009        G2.dyn_dtree[n].Freq = 0;
1010    for (n = 0; n < BL_CODES; n++)
1011        G2.bl_tree[n].Freq = 0;
1012
1013    G2.dyn_ltree[END_BLOCK].Freq = 1;
1014    G2.opt_len = G2.static_len = 0;
1015    G2.last_lit = G2.last_dist = G2.last_flags = 0;
1016    G2.flags = 0;
1017    G2.flag_bit = 1;
1018}
1019
1020
1021/* ===========================================================================
1022 * Restore the heap property by moving down the tree starting at node k,
1023 * exchanging a node with the smallest of its two sons if necessary, stopping
1024 * when the heap property is re-established (each father smaller than its
1025 * two sons).
1026 */
1027
1028/* Compares to subtrees, using the tree depth as tie breaker when
1029 * the subtrees have equal frequency. This minimizes the worst case length. */
1030#define SMALLER(tree, n, m) \
1031    (tree[n].Freq < tree[m].Freq \
1032    || (tree[n].Freq == tree[m].Freq && G2.depth[n] <= G2.depth[m]))
1033
1034static void pqdownheap(ct_data * tree, int k)
1035{
1036    int v = G2.heap[k];
1037    int j = k << 1;     /* left son of k */
1038
1039    while (j <= G2.heap_len) {
1040        /* Set j to the smallest of the two sons: */
1041        if (j < G2.heap_len && SMALLER(tree, G2.heap[j + 1], G2.heap[j]))
1042            j++;
1043
1044        /* Exit if v is smaller than both sons */
1045        if (SMALLER(tree, v, G2.heap[j]))
1046            break;
1047
1048        /* Exchange v with the smallest son */
1049        G2.heap[k] = G2.heap[j];
1050        k = j;
1051
1052        /* And continue down the tree, setting j to the left son of k */
1053        j <<= 1;
1054    }
1055    G2.heap[k] = v;
1056}
1057
1058
1059/* ===========================================================================
1060 * Compute the optimal bit lengths for a tree and update the total bit length
1061 * for the current block.
1062 * IN assertion: the fields freq and dad are set, heap[heap_max] and
1063 *    above are the tree nodes sorted by increasing frequency.
1064 * OUT assertions: the field len is set to the optimal bit length, the
1065 *     array bl_count contains the frequencies for each bit length.
1066 *     The length opt_len is updated; static_len is also updated if stree is
1067 *     not null.
1068 */
1069static void gen_bitlen(tree_desc * desc)
1070{
1071    ct_data *tree = desc->dyn_tree;
1072    const uint8_t *extra = desc->extra_bits;
1073    int base = desc->extra_base;
1074    int max_code = desc->max_code;
1075    int max_length = desc->max_length;
1076    ct_data *stree = desc->static_tree;
1077    int h;              /* heap index */
1078    int n, m;           /* iterate over the tree elements */
1079    int bits;           /* bit length */
1080    int xbits;          /* extra bits */
1081    ush f;              /* frequency */
1082    int overflow = 0;   /* number of elements with bit length too large */
1083
1084    for (bits = 0; bits <= MAX_BITS; bits++)
1085        G2.bl_count[bits] = 0;
1086
1087    /* In a first pass, compute the optimal bit lengths (which may
1088     * overflow in the case of the bit length tree).
1089     */
1090    tree[G2.heap[G2.heap_max]].Len = 0; /* root of the heap */
1091
1092    for (h = G2.heap_max + 1; h < HEAP_SIZE; h++) {
1093        n = G2.heap[h];
1094        bits = tree[tree[n].Dad].Len + 1;
1095        if (bits > max_length) {
1096            bits = max_length;
1097            overflow++;
1098        }
1099        tree[n].Len = (ush) bits;
1100        /* We overwrite tree[n].Dad which is no longer needed */
1101
1102        if (n > max_code)
1103            continue;   /* not a leaf node */
1104
1105        G2.bl_count[bits]++;
1106        xbits = 0;
1107        if (n >= base)
1108            xbits = extra[n - base];
1109        f = tree[n].Freq;
1110        G2.opt_len += (ulg) f *(bits + xbits);
1111
1112        if (stree)
1113            G2.static_len += (ulg) f * (stree[n].Len + xbits);
1114    }
1115    if (overflow == 0)
1116        return;
1117
1118    Trace((stderr, "\nbit length overflow\n"));
1119    /* This happens for example on obj2 and pic of the Calgary corpus */
1120
1121    /* Find the first bit length which could increase: */
1122    do {
1123        bits = max_length - 1;
1124        while (G2.bl_count[bits] == 0)
1125            bits--;
1126        G2.bl_count[bits]--;    /* move one leaf down the tree */
1127        G2.bl_count[bits + 1] += 2; /* move one overflow item as its brother */
1128        G2.bl_count[max_length]--;
1129        /* The brother of the overflow item also moves one step up,
1130         * but this does not affect bl_count[max_length]
1131         */
1132        overflow -= 2;
1133    } while (overflow > 0);
1134
1135    /* Now recompute all bit lengths, scanning in increasing frequency.
1136     * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
1137     * lengths instead of fixing only the wrong ones. This idea is taken
1138     * from 'ar' written by Haruhiko Okumura.)
1139     */
1140    for (bits = max_length; bits != 0; bits--) {
1141        n = G2.bl_count[bits];
1142        while (n != 0) {
1143            m = G2.heap[--h];
1144            if (m > max_code)
1145                continue;
1146            if (tree[m].Len != (unsigned) bits) {
1147                Trace((stderr, "code %d bits %d->%d\n", m, tree[m].Len, bits));
1148                G2.opt_len += ((int32_t) bits - tree[m].Len) * tree[m].Freq;
1149                tree[m].Len = bits;
1150            }
1151            n--;
1152        }
1153    }
1154}
1155
1156
1157/* ===========================================================================
1158 * Generate the codes for a given tree and bit counts (which need not be
1159 * optimal).
1160 * IN assertion: the array bl_count contains the bit length statistics for
1161 * the given tree and the field len is set for all tree elements.
1162 * OUT assertion: the field code is set for all tree elements of non
1163 *     zero code length.
1164 */
1165static void gen_codes(ct_data * tree, int max_code)
1166{
1167    ush next_code[MAX_BITS + 1];    /* next code value for each bit length */
1168    ush code = 0;       /* running code value */
1169    int bits;           /* bit index */
1170    int n;              /* code index */
1171
1172    /* The distribution counts are first used to generate the code values
1173     * without bit reversal.
1174     */
1175    for (bits = 1; bits <= MAX_BITS; bits++) {
1176        next_code[bits] = code = (code + G2.bl_count[bits - 1]) << 1;
1177    }
1178    /* Check that the bit counts in bl_count are consistent. The last code
1179     * must be all ones.
1180     */
1181    Assert(code + G2.bl_count[MAX_BITS] - 1 == (1 << MAX_BITS) - 1,
1182            "inconsistent bit counts");
1183    Tracev((stderr, "\ngen_codes: max_code %d ", max_code));
1184
1185    for (n = 0; n <= max_code; n++) {
1186        int len = tree[n].Len;
1187
1188        if (len == 0)
1189            continue;
1190        /* Now reverse the bits */
1191        tree[n].Code = bi_reverse(next_code[len]++, len);
1192
1193        Tracec(tree != G2.static_ltree,
1194               (stderr, "\nn %3d %c l %2d c %4x (%x) ", n,
1195                (n > ' ' ? n : ' '), len, tree[n].Code,
1196                next_code[len] - 1));
1197    }
1198}
1199
1200
1201/* ===========================================================================
1202 * Construct one Huffman tree and assigns the code bit strings and lengths.
1203 * Update the total bit length for the current block.
1204 * IN assertion: the field freq is set for all tree elements.
1205 * OUT assertions: the fields len and code are set to the optimal bit length
1206 *     and corresponding code. The length opt_len is updated; static_len is
1207 *     also updated if stree is not null. The field max_code is set.
1208 */
1209
1210/* Remove the smallest element from the heap and recreate the heap with
1211 * one less element. Updates heap and heap_len. */
1212
1213#define SMALLEST 1
1214/* Index within the heap array of least frequent node in the Huffman tree */
1215
1216#define PQREMOVE(tree, top) \
1217do { \
1218    top = G2.heap[SMALLEST]; \
1219    G2.heap[SMALLEST] = G2.heap[G2.heap_len--]; \
1220    pqdownheap(tree, SMALLEST); \
1221} while (0)
1222
1223static void build_tree(tree_desc * desc)
1224{
1225    ct_data *tree = desc->dyn_tree;
1226    ct_data *stree = desc->static_tree;
1227    int elems = desc->elems;
1228    int n, m;           /* iterate over heap elements */
1229    int max_code = -1;  /* largest code with non zero frequency */
1230    int node = elems;   /* next internal node of the tree */
1231
1232    /* Construct the initial heap, with least frequent element in
1233     * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
1234     * heap[0] is not used.
1235     */
1236    G2.heap_len = 0;
1237    G2.heap_max = HEAP_SIZE;
1238
1239    for (n = 0; n < elems; n++) {
1240        if (tree[n].Freq != 0) {
1241            G2.heap[++G2.heap_len] = max_code = n;
1242            G2.depth[n] = 0;
1243        } else {
1244            tree[n].Len = 0;
1245        }
1246    }
1247
1248    /* The pkzip format requires that at least one distance code exists,
1249     * and that at least one bit should be sent even if there is only one
1250     * possible code. So to avoid special checks later on we force at least
1251     * two codes of non zero frequency.
1252     */
1253    while (G2.heap_len < 2) {
1254        int new = G2.heap[++G2.heap_len] = (max_code < 2 ? ++max_code : 0);
1255
1256        tree[new].Freq = 1;
1257        G2.depth[new] = 0;
1258        G2.opt_len--;
1259        if (stree)
1260            G2.static_len -= stree[new].Len;
1261        /* new is 0 or 1 so it does not have extra bits */
1262    }
1263    desc->max_code = max_code;
1264
1265    /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
1266     * establish sub-heaps of increasing lengths:
1267     */
1268    for (n = G2.heap_len / 2; n >= 1; n--)
1269        pqdownheap(tree, n);
1270
1271    /* Construct the Huffman tree by repeatedly combining the least two
1272     * frequent nodes.
1273     */
1274    do {
1275        PQREMOVE(tree, n);  /* n = node of least frequency */
1276        m = G2.heap[SMALLEST];  /* m = node of next least frequency */
1277
1278        G2.heap[--G2.heap_max] = n; /* keep the nodes sorted by frequency */
1279        G2.heap[--G2.heap_max] = m;
1280
1281        /* Create a new node father of n and m */
1282        tree[node].Freq = tree[n].Freq + tree[m].Freq;
1283        G2.depth[node] = MAX(G2.depth[n], G2.depth[m]) + 1;
1284        tree[n].Dad = tree[m].Dad = (ush) node;
1285#ifdef DUMP_BL_TREE
1286        if (tree == G2.bl_tree) {
1287            bb_error_msg("\nnode %d(%d), sons %d(%d) %d(%d)",
1288                    node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
1289        }
1290#endif
1291        /* and insert the new node in the heap */
1292        G2.heap[SMALLEST] = node++;
1293        pqdownheap(tree, SMALLEST);
1294
1295    } while (G2.heap_len >= 2);
1296
1297    G2.heap[--G2.heap_max] = G2.heap[SMALLEST];
1298
1299    /* At this point, the fields freq and dad are set. We can now
1300     * generate the bit lengths.
1301     */
1302    gen_bitlen((tree_desc *) desc);
1303
1304    /* The field len is now set, we can generate the bit codes */
1305    gen_codes((ct_data *) tree, max_code);
1306}
1307
1308
1309/* ===========================================================================
1310 * Scan a literal or distance tree to determine the frequencies of the codes
1311 * in the bit length tree. Updates opt_len to take into account the repeat
1312 * counts. (The contribution of the bit length codes will be added later
1313 * during the construction of bl_tree.)
1314 */
1315static void scan_tree(ct_data * tree, int max_code)
1316{
1317    int n;              /* iterates over all tree elements */
1318    int prevlen = -1;   /* last emitted length */
1319    int curlen;         /* length of current code */
1320    int nextlen = tree[0].Len;  /* length of next code */
1321    int count = 0;      /* repeat count of the current code */
1322    int max_count = 7;  /* max repeat count */
1323    int min_count = 4;  /* min repeat count */
1324
1325    if (nextlen == 0) {
1326        max_count = 138;
1327        min_count = 3;
1328    }
1329    tree[max_code + 1].Len = 0xffff; /* guard */
1330
1331    for (n = 0; n <= max_code; n++) {
1332        curlen = nextlen;
1333        nextlen = tree[n + 1].Len;
1334        if (++count < max_count && curlen == nextlen)
1335            continue;
1336
1337        if (count < min_count) {
1338            G2.bl_tree[curlen].Freq += count;
1339        } else if (curlen != 0) {
1340            if (curlen != prevlen)
1341                G2.bl_tree[curlen].Freq++;
1342            G2.bl_tree[REP_3_6].Freq++;
1343        } else if (count <= 10) {
1344            G2.bl_tree[REPZ_3_10].Freq++;
1345        } else {
1346            G2.bl_tree[REPZ_11_138].Freq++;
1347        }
1348        count = 0;
1349        prevlen = curlen;
1350
1351        max_count = 7;
1352        min_count = 4;
1353        if (nextlen == 0) {
1354            max_count = 138;
1355            min_count = 3;
1356        } else if (curlen == nextlen) {
1357            max_count = 6;
1358            min_count = 3;
1359        }
1360    }
1361}
1362
1363
1364/* ===========================================================================
1365 * Send a literal or distance tree in compressed form, using the codes in
1366 * bl_tree.
1367 */
1368static void send_tree(ct_data * tree, int max_code)
1369{
1370    int n;              /* iterates over all tree elements */
1371    int prevlen = -1;   /* last emitted length */
1372    int curlen;         /* length of current code */
1373    int nextlen = tree[0].Len;  /* length of next code */
1374    int count = 0;      /* repeat count of the current code */
1375    int max_count = 7;  /* max repeat count */
1376    int min_count = 4;  /* min repeat count */
1377
1378/* tree[max_code+1].Len = -1; *//* guard already set */
1379    if (nextlen == 0)
1380        max_count = 138, min_count = 3;
1381
1382    for (n = 0; n <= max_code; n++) {
1383        curlen = nextlen;
1384        nextlen = tree[n + 1].Len;
1385        if (++count < max_count && curlen == nextlen) {
1386            continue;
1387        } else if (count < min_count) {
1388            do {
1389                SEND_CODE(curlen, G2.bl_tree);
1390            } while (--count);
1391        } else if (curlen != 0) {
1392            if (curlen != prevlen) {
1393                SEND_CODE(curlen, G2.bl_tree);
1394                count--;
1395            }
1396            Assert(count >= 3 && count <= 6, " 3_6?");
1397            SEND_CODE(REP_3_6, G2.bl_tree);
1398            send_bits(count - 3, 2);
1399        } else if (count <= 10) {
1400            SEND_CODE(REPZ_3_10, G2.bl_tree);
1401            send_bits(count - 3, 3);
1402        } else {
1403            SEND_CODE(REPZ_11_138, G2.bl_tree);
1404            send_bits(count - 11, 7);
1405        }
1406        count = 0;
1407        prevlen = curlen;
1408        if (nextlen == 0) {
1409            max_count = 138;
1410            min_count = 3;
1411        } else if (curlen == nextlen) {
1412            max_count = 6;
1413            min_count = 3;
1414        } else {
1415            max_count = 7;
1416            min_count = 4;
1417        }
1418    }
1419}
1420
1421
1422/* ===========================================================================
1423 * Construct the Huffman tree for the bit lengths and return the index in
1424 * bl_order of the last bit length code to send.
1425 */
1426static int build_bl_tree(void)
1427{
1428    int max_blindex;    /* index of last bit length code of non zero freq */
1429
1430    /* Determine the bit length frequencies for literal and distance trees */
1431    scan_tree(G2.dyn_ltree, G2.l_desc.max_code);
1432    scan_tree(G2.dyn_dtree, G2.d_desc.max_code);
1433
1434    /* Build the bit length tree: */
1435    build_tree(&G2.bl_desc);
1436    /* opt_len now includes the length of the tree representations, except
1437     * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
1438     */
1439
1440    /* Determine the number of bit length codes to send. The pkzip format
1441     * requires that at least 4 bit length codes be sent. (appnote.txt says
1442     * 3 but the actual value used is 4.)
1443     */
1444    for (max_blindex = BL_CODES - 1; max_blindex >= 3; max_blindex--) {
1445        if (G2.bl_tree[bl_order[max_blindex]].Len != 0)
1446            break;
1447    }
1448    /* Update opt_len to include the bit length tree and counts */
1449    G2.opt_len += 3 * (max_blindex + 1) + 5 + 5 + 4;
1450    Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", G2.opt_len, G2.static_len));
1451
1452    return max_blindex;
1453}
1454
1455
1456/* ===========================================================================
1457 * Send the header for a block using dynamic Huffman trees: the counts, the
1458 * lengths of the bit length codes, the literal tree and the distance tree.
1459 * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
1460 */
1461static void send_all_trees(int lcodes, int dcodes, int blcodes)
1462{
1463    int rank;           /* index in bl_order */
1464
1465    Assert(lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");
1466    Assert(lcodes <= L_CODES && dcodes <= D_CODES
1467           && blcodes <= BL_CODES, "too many codes");
1468    Tracev((stderr, "\nbl counts: "));
1469    send_bits(lcodes - 257, 5); /* not +255 as stated in appnote.txt */
1470    send_bits(dcodes - 1, 5);
1471    send_bits(blcodes - 4, 4);  /* not -3 as stated in appnote.txt */
1472    for (rank = 0; rank < blcodes; rank++) {
1473        Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
1474        send_bits(G2.bl_tree[bl_order[rank]].Len, 3);
1475    }
1476    Tracev((stderr, "\nbl tree: sent %ld", G1.bits_sent));
1477
1478    send_tree((ct_data *) G2.dyn_ltree, lcodes - 1);    /* send the literal tree */
1479    Tracev((stderr, "\nlit tree: sent %ld", G1.bits_sent));
1480
1481    send_tree((ct_data *) G2.dyn_dtree, dcodes - 1);    /* send the distance tree */
1482    Tracev((stderr, "\ndist tree: sent %ld", G1.bits_sent));
1483}
1484
1485
1486/* ===========================================================================
1487 * Save the match info and tally the frequency counts. Return true if
1488 * the current block must be flushed.
1489 */
1490static int ct_tally(int dist, int lc)
1491{
1492    G1.l_buf[G2.last_lit++] = lc;
1493    if (dist == 0) {
1494        /* lc is the unmatched char */
1495        G2.dyn_ltree[lc].Freq++;
1496    } else {
1497        /* Here, lc is the match length - MIN_MATCH */
1498        dist--;         /* dist = match distance - 1 */
1499        Assert((ush) dist < (ush) MAX_DIST
1500         && (ush) lc <= (ush) (MAX_MATCH - MIN_MATCH)
1501         && (ush) D_CODE(dist) < (ush) D_CODES, "ct_tally: bad match"
1502        );
1503
1504        G2.dyn_ltree[G2.length_code[lc] + LITERALS + 1].Freq++;
1505        G2.dyn_dtree[D_CODE(dist)].Freq++;
1506
1507        G1.d_buf[G2.last_dist++] = dist;
1508        G2.flags |= G2.flag_bit;
1509    }
1510    G2.flag_bit <<= 1;
1511
1512    /* Output the flags if they fill a byte: */
1513    if ((G2.last_lit & 7) == 0) {
1514        G2.flag_buf[G2.last_flags++] = G2.flags;
1515        G2.flags = 0;
1516        G2.flag_bit = 1;
1517    }
1518    /* Try to guess if it is profitable to stop the current block here */
1519    if ((G2.last_lit & 0xfff) == 0) {
1520        /* Compute an upper bound for the compressed length */
1521        ulg out_length = G2.last_lit * 8L;
1522        ulg in_length = (ulg) G1.strstart - G1.block_start;
1523        int dcode;
1524
1525        for (dcode = 0; dcode < D_CODES; dcode++) {
1526            out_length += G2.dyn_dtree[dcode].Freq * (5L + extra_dbits[dcode]);
1527        }
1528        out_length >>= 3;
1529        Trace((stderr,
1530                "\nlast_lit %u, last_dist %u, in %ld, out ~%ld(%ld%%) ",
1531                G2.last_lit, G2.last_dist, in_length, out_length,
1532                100L - out_length * 100L / in_length));
1533        if (G2.last_dist < G2.last_lit / 2 && out_length < in_length / 2)
1534            return 1;
1535    }
1536    return (G2.last_lit == LIT_BUFSIZE - 1 || G2.last_dist == DIST_BUFSIZE);
1537    /* We avoid equality with LIT_BUFSIZE because of wraparound at 64K
1538     * on 16 bit machines and because stored blocks are restricted to
1539     * 64K-1 bytes.
1540     */
1541}
1542
1543/* ===========================================================================
1544 * Send the block data compressed using the given Huffman trees
1545 */
1546static void compress_block(ct_data * ltree, ct_data * dtree)
1547{
1548    unsigned dist;          /* distance of matched string */
1549    int lc;                 /* match length or unmatched char (if dist == 0) */
1550    unsigned lx = 0;        /* running index in l_buf */
1551    unsigned dx = 0;        /* running index in d_buf */
1552    unsigned fx = 0;        /* running index in flag_buf */
1553    uch flag = 0;           /* current flags */
1554    unsigned code;          /* the code to send */
1555    int extra;              /* number of extra bits to send */
1556
1557    if (G2.last_lit != 0) do {
1558        if ((lx & 7) == 0)
1559            flag = G2.flag_buf[fx++];
1560        lc = G1.l_buf[lx++];
1561        if ((flag & 1) == 0) {
1562            SEND_CODE(lc, ltree);   /* send a literal byte */
1563            Tracecv(lc > ' ', (stderr, " '%c' ", lc));
1564        } else {
1565            /* Here, lc is the match length - MIN_MATCH */
1566            code = G2.length_code[lc];
1567            SEND_CODE(code + LITERALS + 1, ltree);  /* send the length code */
1568            extra = extra_lbits[code];
1569            if (extra != 0) {
1570                lc -= G2.base_length[code];
1571                send_bits(lc, extra);   /* send the extra length bits */
1572            }
1573            dist = G1.d_buf[dx++];
1574            /* Here, dist is the match distance - 1 */
1575            code = D_CODE(dist);
1576            Assert(code < D_CODES, "bad d_code");
1577
1578            SEND_CODE(code, dtree); /* send the distance code */
1579            extra = extra_dbits[code];
1580            if (extra != 0) {
1581                dist -= G2.base_dist[code];
1582                send_bits(dist, extra); /* send the extra distance bits */
1583            }
1584        }           /* literal or match pair ? */
1585        flag >>= 1;
1586    } while (lx < G2.last_lit);
1587
1588    SEND_CODE(END_BLOCK, ltree);
1589}
1590
1591
1592/* ===========================================================================
1593 * Determine the best encoding for the current block: dynamic trees, static
1594 * trees or store, and output the encoded block to the zip file. This function
1595 * returns the total compressed length for the file so far.
1596 */
1597static ulg flush_block(char *buf, ulg stored_len, int eof)
1598{
1599    ulg opt_lenb, static_lenb;      /* opt_len and static_len in bytes */
1600    int max_blindex;                /* index of last bit length code of non zero freq */
1601
1602    G2.flag_buf[G2.last_flags] = G2.flags;   /* Save the flags for the last 8 items */
1603
1604    /* Construct the literal and distance trees */
1605    build_tree(&G2.l_desc);
1606    Tracev((stderr, "\nlit data: dyn %ld, stat %ld", G2.opt_len, G2.static_len));
1607
1608    build_tree(&G2.d_desc);
1609    Tracev((stderr, "\ndist data: dyn %ld, stat %ld", G2.opt_len, G2.static_len));
1610    /* At this point, opt_len and static_len are the total bit lengths of
1611     * the compressed block data, excluding the tree representations.
1612     */
1613
1614    /* Build the bit length tree for the above two trees, and get the index
1615     * in bl_order of the last bit length code to send.
1616     */
1617    max_blindex = build_bl_tree();
1618
1619    /* Determine the best encoding. Compute first the block length in bytes */
1620    opt_lenb = (G2.opt_len + 3 + 7) >> 3;
1621    static_lenb = (G2.static_len + 3 + 7) >> 3;
1622
1623    Trace((stderr,
1624            "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u dist %u ",
1625            opt_lenb, G2.opt_len, static_lenb, G2.static_len, stored_len,
1626            G2.last_lit, G2.last_dist));
1627
1628    if (static_lenb <= opt_lenb)
1629        opt_lenb = static_lenb;
1630
1631    /* If compression failed and this is the first and last block,
1632     * and if the zip file can be seeked (to rewrite the local header),
1633     * the whole file is transformed into a stored file:
1634     */
1635    if (stored_len <= opt_lenb && eof && G2.compressed_len == 0L && seekable()) {
1636        /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */
1637        if (buf == NULL)
1638            bb_error_msg("block vanished");
1639
1640        copy_block(buf, (unsigned) stored_len, 0);  /* without header */
1641        G2.compressed_len = stored_len << 3;
1642
1643    } else if (stored_len + 4 <= opt_lenb && buf != NULL) {
1644        /* 4: two words for the lengths */
1645        /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
1646         * Otherwise we can't have processed more than WSIZE input bytes since
1647         * the last block flush, because compression would have been
1648         * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
1649         * transform a block into a stored block.
1650         */
1651        send_bits((STORED_BLOCK << 1) + eof, 3);    /* send block type */
1652        G2.compressed_len = (G2.compressed_len + 3 + 7) & ~7L;
1653        G2.compressed_len += (stored_len + 4) << 3;
1654
1655        copy_block(buf, (unsigned) stored_len, 1);  /* with header */
1656
1657    } else if (static_lenb == opt_lenb) {
1658        send_bits((STATIC_TREES << 1) + eof, 3);
1659        compress_block((ct_data *) G2.static_ltree, (ct_data *) G2.static_dtree);
1660        G2.compressed_len += 3 + G2.static_len;
1661    } else {
1662        send_bits((DYN_TREES << 1) + eof, 3);
1663        send_all_trees(G2.l_desc.max_code + 1, G2.d_desc.max_code + 1,
1664                    max_blindex + 1);
1665        compress_block((ct_data *) G2.dyn_ltree, (ct_data *) G2.dyn_dtree);
1666        G2.compressed_len += 3 + G2.opt_len;
1667    }
1668    Assert(G2.compressed_len == G1.bits_sent, "bad compressed size");
1669    init_block();
1670
1671    if (eof) {
1672        bi_windup();
1673        G2.compressed_len += 7; /* align on byte boundary */
1674    }
1675    Tracev((stderr, "\ncomprlen %lu(%lu) ", G2.compressed_len >> 3,
1676            G2.compressed_len - 7 * eof));
1677
1678    return G2.compressed_len >> 3;
1679}
1680
1681
1682/* ===========================================================================
1683 * Update a hash value with the given input byte
1684 * IN  assertion: all calls to UPDATE_HASH are made with consecutive
1685 *    input characters, so that a running hash key can be computed from the
1686 *    previous key instead of complete recalculation each time.
1687 */
1688#define UPDATE_HASH(h, c) (h = (((h)<<H_SHIFT) ^ (c)) & HASH_MASK)
1689
1690
1691/* ===========================================================================
1692 * Same as above, but achieves better compression. We use a lazy
1693 * evaluation for matches: a match is finally adopted only if there is
1694 * no better match at the next window position.
1695 *
1696 * Processes a new input file and return its compressed length. Sets
1697 * the compressed length, crc, deflate flags and internal file
1698 * attributes.
1699 */
1700
1701/* Flush the current block, with given end-of-file flag.
1702 * IN assertion: strstart is set to the end of the current match. */
1703#define FLUSH_BLOCK(eof) \
1704    flush_block( \
1705        G1.block_start >= 0L \
1706            ? (char*)&G1.window[(unsigned)G1.block_start] \
1707            : (char*)NULL, \
1708        (ulg)G1.strstart - G1.block_start, \
1709        (eof) \
1710    )
1711
1712/* Insert string s in the dictionary and set match_head to the previous head
1713 * of the hash chain (the most recent string with same hash key). Return
1714 * the previous length of the hash chain.
1715 * IN  assertion: all calls to INSERT_STRING are made with consecutive
1716 *    input characters and the first MIN_MATCH bytes of s are valid
1717 *    (except for the last MIN_MATCH-1 bytes of the input file). */
1718#define INSERT_STRING(s, match_head) \
1719do { \
1720    UPDATE_HASH(G1.ins_h, G1.window[(s) + MIN_MATCH-1]); \
1721    G1.prev[(s) & WMASK] = match_head = head[G1.ins_h]; \
1722    head[G1.ins_h] = (s); \
1723} while (0)
1724
1725static ulg deflate(void)
1726{
1727    IPos hash_head;     /* head of hash chain */
1728    IPos prev_match;    /* previous match */
1729    int flush;          /* set if current block must be flushed */
1730    int match_available = 0;    /* set if previous match exists */
1731    unsigned match_length = MIN_MATCH - 1;  /* length of best match */
1732
1733    /* Process the input block. */
1734    while (G1.lookahead != 0) {
1735        /* Insert the string window[strstart .. strstart+2] in the
1736         * dictionary, and set hash_head to the head of the hash chain:
1737         */
1738        INSERT_STRING(G1.strstart, hash_head);
1739
1740        /* Find the longest match, discarding those <= prev_length.
1741         */
1742        G1.prev_length = match_length;
1743        prev_match = G1.match_start;
1744        match_length = MIN_MATCH - 1;
1745
1746        if (hash_head != 0 && G1.prev_length < max_lazy_match
1747         && G1.strstart - hash_head <= MAX_DIST
1748        ) {
1749            /* To simplify the code, we prevent matches with the string
1750             * of window index 0 (in particular we have to avoid a match
1751             * of the string with itself at the start of the input file).
1752             */
1753            match_length = longest_match(hash_head);
1754            /* longest_match() sets match_start */
1755            if (match_length > G1.lookahead)
1756                match_length = G1.lookahead;
1757
1758            /* Ignore a length 3 match if it is too distant: */
1759            if (match_length == MIN_MATCH && G1.strstart - G1.match_start > TOO_FAR) {
1760                /* If prev_match is also MIN_MATCH, G1.match_start is garbage
1761                 * but we will ignore the current match anyway.
1762                 */
1763                match_length--;
1764            }
1765        }
1766        /* If there was a match at the previous step and the current
1767         * match is not better, output the previous match:
1768         */
1769        if (G1.prev_length >= MIN_MATCH && match_length <= G1.prev_length) {
1770            check_match(G1.strstart - 1, prev_match, G1.prev_length);
1771            flush = ct_tally(G1.strstart - 1 - prev_match, G1.prev_length - MIN_MATCH);
1772
1773            /* Insert in hash table all strings up to the end of the match.
1774             * strstart-1 and strstart are already inserted.
1775             */
1776            G1.lookahead -= G1.prev_length - 1;
1777            G1.prev_length -= 2;
1778            do {
1779                G1.strstart++;
1780                INSERT_STRING(G1.strstart, hash_head);
1781                /* strstart never exceeds WSIZE-MAX_MATCH, so there are
1782                 * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
1783                 * these bytes are garbage, but it does not matter since the
1784                 * next lookahead bytes will always be emitted as literals.
1785                 */
1786            } while (--G1.prev_length != 0);
1787            match_available = 0;
1788            match_length = MIN_MATCH - 1;
1789            G1.strstart++;
1790            if (flush) {
1791                FLUSH_BLOCK(0);
1792                G1.block_start = G1.strstart;
1793            }
1794        } else if (match_available) {
1795            /* If there was no match at the previous position, output a
1796             * single literal. If there was a match but the current match
1797             * is longer, truncate the previous match to a single literal.
1798             */
1799            Tracevv((stderr, "%c", G1.window[G1.strstart - 1]));
1800            if (ct_tally(0, G1.window[G1.strstart - 1])) {
1801                FLUSH_BLOCK(0);
1802                G1.block_start = G1.strstart;
1803            }
1804            G1.strstart++;
1805            G1.lookahead--;
1806        } else {
1807            /* There is no previous match to compare with, wait for
1808             * the next step to decide.
1809             */
1810            match_available = 1;
1811            G1.strstart++;
1812            G1.lookahead--;
1813        }
1814        Assert(G1.strstart <= G1.isize && lookahead <= G1.isize, "a bit too far");
1815
1816        /* Make sure that we always have enough lookahead, except
1817         * at the end of the input file. We need MAX_MATCH bytes
1818         * for the next match, plus MIN_MATCH bytes to insert the
1819         * string following the next match.
1820         */
1821        while (G1.lookahead < MIN_LOOKAHEAD && !G1.eofile)
1822            fill_window();
1823    }
1824    if (match_available)
1825        ct_tally(0, G1.window[G1.strstart - 1]);
1826
1827    return FLUSH_BLOCK(1);  /* eof */
1828}
1829
1830
1831/* ===========================================================================
1832 * Initialize the bit string routines.
1833 */
1834static void bi_init(void)
1835{
1836    G1.bi_buf = 0;
1837    G1.bi_valid = 0;
1838#ifdef DEBUG
1839    G1.bits_sent = 0L;
1840#endif
1841}
1842
1843
1844/* ===========================================================================
1845 * Initialize the "longest match" routines for a new file
1846 */
1847static void lm_init(ush * flagsp)
1848{
1849    unsigned j;
1850
1851    /* Initialize the hash table. */
1852    memset(head, 0, HASH_SIZE * sizeof(*head));
1853    /* prev will be initialized on the fly */
1854
1855    /* speed options for the general purpose bit flag */
1856    *flagsp |= 2;   /* FAST 4, SLOW 2 */
1857    /* ??? reduce max_chain_length for binary files */
1858
1859    G1.strstart = 0;
1860    G1.block_start = 0L;
1861
1862    G1.lookahead = file_read(G1.window,
1863            sizeof(int) <= 2 ? (unsigned) WSIZE : 2 * WSIZE);
1864
1865    if (G1.lookahead == 0 || G1.lookahead == (unsigned) -1) {
1866        G1.eofile = 1;
1867        G1.lookahead = 0;
1868        return;
1869    }
1870    G1.eofile = 0;
1871    /* Make sure that we always have enough lookahead. This is important
1872     * if input comes from a device such as a tty.
1873     */
1874    while (G1.lookahead < MIN_LOOKAHEAD && !G1.eofile)
1875        fill_window();
1876
1877    G1.ins_h = 0;
1878    for (j = 0; j < MIN_MATCH - 1; j++)
1879        UPDATE_HASH(G1.ins_h, G1.window[j]);
1880    /* If lookahead < MIN_MATCH, ins_h is garbage, but this is
1881     * not important since only literal bytes will be emitted.
1882     */
1883}
1884
1885
1886/* ===========================================================================
1887 * Allocate the match buffer, initialize the various tables and save the
1888 * location of the internal file attribute (ascii/binary) and method
1889 * (DEFLATE/STORE).
1890 * One callsite in zip()
1891 */
1892static void ct_init(void)
1893{
1894    int n;              /* iterates over tree elements */
1895    int length;         /* length value */
1896    int code;           /* code value */
1897    int dist;           /* distance index */
1898
1899    G2.compressed_len = 0L;
1900
1901#ifdef NOT_NEEDED
1902    if (G2.static_dtree[0].Len != 0)
1903        return;         /* ct_init already called */
1904#endif
1905
1906    /* Initialize the mapping length (0..255) -> length code (0..28) */
1907    length = 0;
1908    for (code = 0; code < LENGTH_CODES - 1; code++) {
1909        G2.base_length[code] = length;
1910        for (n = 0; n < (1 << extra_lbits[code]); n++) {
1911            G2.length_code[length++] = code;
1912        }
1913    }
1914    Assert(length == 256, "ct_init: length != 256");
1915    /* Note that the length 255 (match length 258) can be represented
1916     * in two different ways: code 284 + 5 bits or code 285, so we
1917     * overwrite length_code[255] to use the best encoding:
1918     */
1919    G2.length_code[length - 1] = code;
1920
1921    /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
1922    dist = 0;
1923    for (code = 0; code < 16; code++) {
1924        G2.base_dist[code] = dist;
1925        for (n = 0; n < (1 << extra_dbits[code]); n++) {
1926            G2.dist_code[dist++] = code;
1927        }
1928    }
1929    Assert(dist == 256, "ct_init: dist != 256");
1930    dist >>= 7;         /* from now on, all distances are divided by 128 */
1931    for (; code < D_CODES; code++) {
1932        G2.base_dist[code] = dist << 7;
1933        for (n = 0; n < (1 << (extra_dbits[code] - 7)); n++) {
1934            G2.dist_code[256 + dist++] = code;
1935        }
1936    }
1937    Assert(dist == 256, "ct_init: 256+dist != 512");
1938
1939    /* Construct the codes of the static literal tree */
1940    /* already zeroed - it's in bss
1941    for (n = 0; n <= MAX_BITS; n++)
1942        G2.bl_count[n] = 0; */
1943
1944    n = 0;
1945    while (n <= 143) {
1946        G2.static_ltree[n++].Len = 8;
1947        G2.bl_count[8]++;
1948    }
1949    while (n <= 255) {
1950        G2.static_ltree[n++].Len = 9;
1951        G2.bl_count[9]++;
1952    }
1953    while (n <= 279) {
1954        G2.static_ltree[n++].Len = 7;
1955        G2.bl_count[7]++;
1956    }
1957    while (n <= 287) {
1958        G2.static_ltree[n++].Len = 8;
1959        G2.bl_count[8]++;
1960    }
1961    /* Codes 286 and 287 do not exist, but we must include them in the
1962     * tree construction to get a canonical Huffman tree (longest code
1963     * all ones)
1964     */
1965    gen_codes((ct_data *) G2.static_ltree, L_CODES + 1);
1966
1967    /* The static distance tree is trivial: */
1968    for (n = 0; n < D_CODES; n++) {
1969        G2.static_dtree[n].Len = 5;
1970        G2.static_dtree[n].Code = bi_reverse(n, 5);
1971    }
1972
1973    /* Initialize the first block of the first file: */
1974    init_block();
1975}
1976
1977
1978/* ===========================================================================
1979 * Deflate in to out.
1980 * IN assertions: the input and output buffers are cleared.
1981 */
1982
1983static void zip(ulg time_stamp)
1984{
1985    ush deflate_flags = 0;  /* pkzip -es, -en or -ex equivalent */
1986
1987    G1.outcnt = 0;
1988
1989    /* Write the header to the gzip file. See algorithm.doc for the format */
1990    /* magic header for gzip files: 1F 8B */
1991    /* compression method: 8 (DEFLATED) */
1992    /* general flags: 0 */
1993    put_32bit(0x00088b1f);
1994    put_32bit(time_stamp);
1995
1996    /* Write deflated file to zip file */
1997    G1.crc = ~0;
1998
1999    bi_init();
2000    ct_init();
2001    lm_init(&deflate_flags);
2002
2003    put_8bit(deflate_flags);    /* extra flags */
2004    put_8bit(3);    /* OS identifier = 3 (Unix) */
2005
2006    deflate();
2007
2008    /* Write the crc and uncompressed size */
2009    put_32bit(~G1.crc);
2010    put_32bit(G1.isize);
2011
2012    flush_outbuf();
2013}
2014
2015
2016/* ======================================================================== */
2017static
2018IF_DESKTOP(long long) int FAST_FUNC pack_gzip(transformer_aux_data_t *aux UNUSED_PARAM)
2019{
2020    struct stat s;
2021
2022    /* Clear input and output buffers */
2023    G1.outcnt = 0;
2024#ifdef DEBUG
2025    G1.insize = 0;
2026#endif
2027    G1.isize = 0;
2028
2029    /* Reinit G2.xxx */
2030    memset(&G2, 0, sizeof(G2));
2031    G2.l_desc.dyn_tree     = G2.dyn_ltree;
2032    G2.l_desc.static_tree  = G2.static_ltree;
2033    G2.l_desc.extra_bits   = extra_lbits;
2034    G2.l_desc.extra_base   = LITERALS + 1;
2035    G2.l_desc.elems        = L_CODES;
2036    G2.l_desc.max_length   = MAX_BITS;
2037    //G2.l_desc.max_code     = 0;
2038    G2.d_desc.dyn_tree     = G2.dyn_dtree;
2039    G2.d_desc.static_tree  = G2.static_dtree;
2040    G2.d_desc.extra_bits   = extra_dbits;
2041    //G2.d_desc.extra_base   = 0;
2042    G2.d_desc.elems        = D_CODES;
2043    G2.d_desc.max_length   = MAX_BITS;
2044    //G2.d_desc.max_code     = 0;
2045    G2.bl_desc.dyn_tree    = G2.bl_tree;
2046    //G2.bl_desc.static_tree = NULL;
2047    G2.bl_desc.extra_bits  = extra_blbits,
2048    //G2.bl_desc.extra_base  = 0;
2049    G2.bl_desc.elems       = BL_CODES;
2050    G2.bl_desc.max_length  = MAX_BL_BITS;
2051    //G2.bl_desc.max_code    = 0;
2052
2053    s.st_ctime = 0;
2054    fstat(STDIN_FILENO, &s);
2055    zip(s.st_ctime);
2056    return 0;
2057}
2058
2059#if ENABLE_FEATURE_GZIP_LONG_OPTIONS
2060static const char gzip_longopts[] ALIGN1 =
2061    "stdout\0"              No_argument       "c"
2062    "to-stdout\0"           No_argument       "c"
2063    "force\0"               No_argument       "f"
2064    "verbose\0"             No_argument       "v"
2065#if ENABLE_GUNZIP
2066    "decompress\0"          No_argument       "d"
2067    "uncompress\0"          No_argument       "d"
2068    "test\0"                No_argument       "t"
2069#endif
2070    "quiet\0"               No_argument       "q"
2071    "fast\0"                No_argument       "1"
2072    "best\0"                No_argument       "9"
2073    ;
2074#endif
2075
2076/*
2077 * Linux kernel build uses gzip -d -n. We accept and ignore -n.
2078 * Man page says:
2079 * -n --no-name
2080 * gzip: do not save the original file name and time stamp.
2081 * (The original name is always saved if the name had to be truncated.)
2082 * gunzip: do not restore the original file name/time even if present
2083 * (remove only the gzip suffix from the compressed file name).
2084 * This option is the default when decompressing.
2085 * -N --name
2086 * gzip: always save the original file name and time stamp (this is the default)
2087 * gunzip: restore the original file name and time stamp if present.
2088 */
2089
2090int gzip_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
2091#if ENABLE_GUNZIP
2092int gzip_main(int argc, char **argv)
2093#else
2094int gzip_main(int argc UNUSED_PARAM, char **argv)
2095#endif
2096{
2097    unsigned opt;
2098
2099#if ENABLE_FEATURE_GZIP_LONG_OPTIONS
2100    applet_long_options = gzip_longopts;
2101#endif
2102    /* Must match bbunzip's constants OPT_STDOUT, OPT_FORCE! */
2103    opt = getopt32(argv, "cfv" IF_GUNZIP("dt") "q123456789n");
2104#if ENABLE_GUNZIP /* gunzip_main may not be visible... */
2105    if (opt & 0x18) // -d and/or -t
2106        return gunzip_main(argc, argv);
2107#endif
2108    option_mask32 &= 0x7; /* ignore -q, -0..9 */
2109    //if (opt & 0x1) // -c
2110    //if (opt & 0x2) // -f
2111    //if (opt & 0x4) // -v
2112    argv += optind;
2113
2114    SET_PTR_TO_GLOBALS((char *)xzalloc(sizeof(struct globals)+sizeof(struct globals2))
2115            + sizeof(struct globals));
2116
2117    /* Allocate all global buffers (for DYN_ALLOC option) */
2118    ALLOC(uch, G1.l_buf, INBUFSIZ);
2119    ALLOC(uch, G1.outbuf, OUTBUFSIZ);
2120    ALLOC(ush, G1.d_buf, DIST_BUFSIZE);
2121    ALLOC(uch, G1.window, 2L * WSIZE);
2122    ALLOC(ush, G1.prev, 1L << BITS);
2123
2124    /* Initialize the CRC32 table */
2125    global_crc32_table = crc32_filltable(NULL, 0);
2126
2127    return bbunpack(argv, pack_gzip, append_ext, "gz");
2128}
Note: See TracBrowser for help on using the repository browser.