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

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