Ignore:
Timestamp:
Nov 6, 2007, 11:01:53 AM (16 years ago)
Author:
Bruno Cornec
Message:
  • Better output for mindi-busybox revision
  • Remove dummy file created on NFS - report from Arnaud Tiger <arnaud.tiger_at_hp.com>
  • strace useful for debug
  • fix new versions for pb (2.0.0 for mindi and 1.7.2 for mindi-busybox)
  • fix build process for mindi-busybox + options used in that version (dd for label-partitions-as-necessary)
  • fix typo in label-partitions-as-necessary which doesn't seem to work
  • Update to busybox 1.7.2
  • perl is now required at restore time to support uuid swap partitions (and will be used for many other thigs

in the future for sure)

  • next mindi version will be 2.0.0 due to all the changes made in it (udev may break working distros)
  • small optimization in mindi on keyboard handling (one single find instead of multiple)
  • better interaction for USB device when launching mindi manually
  • attempt to automatically guess block disk size for ramdisk
  • fix typos in bkphw
  • Fix the remaining problem with UUID support for swap partitions
  • Updates mondoarchive man page for USB support
  • Adds preliminary Hardware support to mindi (Proliant SSSTK)
  • Tries to add udev support also for rhel4
  • Fix UUID support which was still broken.
  • Be conservative in test for the start-nfs script
  • Update config file for mindi-busybox for 1.7.2 migration
  • Try to run around a busybox bug (1.2.2 pb on inexistant links)
  • Add build content for mindi-busybox in pb
  • Remove distributions content for mindi-busybox
  • Fix a warning on inexistant raidtab
  • Solve problem on tmpfs in restore init (Problem of inexistant symlink and busybox)
  • Create MONDO_CACHE and use it everywhere + creation at start
  • Really never try to eject a USB device
  • Fix a issue with &> usage (replaced with 1> and 2>)
  • Adds magic file to depllist in order to have file working + ldd which helps for debugging issues
  • tty modes correct to avoid sh error messages
  • Use ext3 normally and not ext2 instead
  • USB device should be corrected after reading (take 1st part)
  • Adds a mount_USB_here function derived from mount_CDROM_here
  • usb detection place before /dev detection in device name at restore time
  • Fix when restoring from USB: media is asked in interactive mode
  • Adds USB support for mondorestore
  • mount_cdrom => mount_media
  • elilo.efi is now searched throughout /boot/efi and not in a fixed place as there is no standard
  • untar-and-softlink => untar (+ interface change)
  • suppress useless softlinks creation/removal in boot process
  • avoids udevd messages on groups
  • Increase # of disks to 99 as in mindi at restore time (should be a conf file parameter)
  • skip existing big file creation
  • seems to work correctly for USB mindi boot
  • Adds group and tty link to udev conf
  • Always load usb-torage (even 2.6) to initiate USB bus discovery
  • Better printing of messages
  • Attempt to fix a bug in supporting OpenSusE 10.3 kernel for initramfs (mindi may now use multiple regex for kernel initrd detection)
  • Links were not correctly done as non relative for modules in mindi
  • exclusion of modules denied now works
  • Also create modules in their ordinary place, so that classical modprobe works + copy modules.dep
  • Fix bugs for DENY_MODS handling
  • Add device /dev/console for udev
  • ide-generic should now really be excluded
  • Fix a bug in major number for tty
  • If udev then adds modprobe/insmod to rootfs
  • tty0 is also cretaed with udev
  • ide-generic put rather in DENY_MODS
  • udevd remove from deplist s handled in mindi directly
  • better default for mindi when using --usb
  • Handles dynamically linked busybox (in case we want to use it soon ;-)
  • Adds fixed devices to create for udev
  • ide-generic should not be part of the initrd when using libata v2
  • support a dynamically linked udev (case on Ubuntu 7.10 and Mandriva 2008.0 so should be quite generic) This will give incitation to move to dyn. linked binaries in the initrd which will help for other tasks (ia6 4)
  • Improvement in udev support (do not use cl options not available in busybox)
  • Udev in mindi
    • auto creation of the right links at boot time with udev-links.conf(from Mandriva 2008.0)
    • rework startup of udev as current makes kernel crash (from Mandriva 2008.0)
    • add support for 64 bits udev
  • Try to render MyInsmod silent at boot time
  • Adds udev support (mandatory for newest distributions to avoid remapping of devices in a different way as on the original system)
  • We also need vaft format support for USB boot
  • Adds libusual support (Ubuntu 7.10 needs it for USB)
  • Improve Ubuntu/Debian keyboard detection and support
  • pbinit adapted to new pb (0.8.10). Filtering of docs done in it
  • Suppress some mondo warnings and errors on USB again
  • Tries to fix lack of files in deb mindi package
  • Verify should now work for USB devices
  • More log/mesages improvement for USB support
  • - Supress g_erase_tmpdir_and_scratchdir
  • Improve some log messages for USB support
  • Try to improve install in mindi to avoid issues with isolinux.cfg not installed vene if in the pkg :-(
  • Improve mindi-busybox build
  • In conformity with pb 0.8.9
  • Add support for Ubuntu 7.10 in build process
  • Add USB Key button to Menu UI (CD streamer removed)
  • Attempt to fix error messages on tmp/scratch files at the end by removing those dir at the latest possible.
  • Fix a bug linked to the size of the -E param which could be used (Arnaud Tiger/René Ribaud).
  • Integrate ~/.pbrc content into mondorescue.pb (required project-builder >= 0.8.7)
  • Put mondorescue in conformity with new pb filtering rules
  • Add USB support at restore time (no test done yet). New start-usb script PB varibale added where useful
  • Unmounting USB device before removal of temporary scratchdir
  • Stil refining USB copy back to mondo (one command was not executed)
  • No need to have the image subdor in the csratchdir when USB.
  • umount the USB partition before attempting to use it
  • Remove useless copy from mindi to mondo at end of USB handling

(risky merge, we are raising the limits of 2 diverging branches. The status of stable is not completely sure as such. Will need lots of tests, but it's not yet done :-()
(merge -r1692:1769 $SVN_M/branches/2.2.5)

File:
1 edited

Legend:

Unmodified
Added
Removed

  • branches/stable/mindi-busybox/archival/gzip.c

    r821 r1770  
    66 *
    77 * 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."
     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."
    1111 *
    1212 * Adjusted further by Erik Andersen <andersen@codepoet.org> to support
    … …  
    1717 */
    1818
     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
     44
     45/* ===========================================================================
     46 */
     47//#define DEBUG 1
     48/* Diagnostic functions */
     49#ifdef DEBUG
     50#  define Assert(cond,msg) { if (!(cond)) bb_error_msg(msg); }
     51#  define Trace(x) fprintf x
     52#  define Tracev(x) {if (verbose) fprintf x; }
     53#  define Tracevv(x) {if (verbose > 1) fprintf x; }
     54#  define Tracec(c,x) {if (verbose && (c)) fprintf x; }
     55#  define Tracecv(c,x) {if (verbose > 1 && (c)) fprintf x; }
     56#else
     57#  define Assert(cond,msg)
     58#  define Trace(x)
     59#  define Tracev(x)
     60#  define Tracevv(x)
     61#  define Tracec(c,x)
     62#  define Tracecv(c,x)
     63#endif
     64
     65
     66/* ===========================================================================
     67 */
    1968#define SMALL_MEM
    20 
    21 #include <stdlib.h>
    22 #include <stdio.h>
    23 #include <string.h>
    24 #include <unistd.h>
    25 #include <errno.h>
    26 #include <sys/types.h>
    27 #include <signal.h>
    28 #include <utime.h>
    29 #include <ctype.h>
    30 #include <sys/types.h>
    31 #include <unistd.h>
    32 #include <dirent.h>
    33 #include <fcntl.h>
    34 #include <time.h>
    35 #include "busybox.h"
    36 
    37 typedef unsigned char uch;
    38 typedef unsigned short ush;
    39 typedef unsigned long ulg;
    40 
    41 /* Return codes from gzip */
    42 #define OK      0
    43 #define ERROR   1
    44 #define WARNING 2
    45 
    46 /* Compression methods (see algorithm.doc) */
    47 /* Only STORED and DEFLATED are supported by this BusyBox module */
    48 #define STORED      0
    49 /* methods 4 to 7 reserved */
    50 #define DEFLATED    8
    51 
    52 /* To save memory for 16 bit systems, some arrays are overlaid between
    53  * the various modules:
    54  * deflate:  prev+head   window      d_buf  l_buf  outbuf
    55  * unlzw:    tab_prefix  tab_suffix  stack  inbuf  outbuf
    56  * For compression, input is done in window[]. For decompression, output
    57  * is done in window except for unlzw.
    58  */
    5969
    6070#ifndef INBUFSIZ
    … …  
    6575#  endif
    6676#endif
    67 #define INBUF_EXTRA  64 /* required by unlzw() */
    6877
    6978#ifndef OUTBUFSIZ
    … …  
    7483#  endif
    7584#endif
    76 #define OUTBUF_EXTRA 2048   /* required by unlzw() */
    7785
    7886#ifndef DIST_BUFSIZE
    … …  
    8391#  endif
    8492#endif
    85 
    86 #  define DECLARE(type, array, size)  static type * array
    87 #  define ALLOC(type, array, size) { \
    88       array = (type*)xzalloc((size_t)(((size)+1L)/2) * 2*sizeof(type)); \
    89    }
    90 #  define FREE(array) {free(array), array=NULL;}
    91 
    92 #define tab_suffix window
    93 #define tab_prefix prev /* hash link (see deflate.c) */
    94 #define head (prev+WSIZE)   /* hash head (see deflate.c) */
    95 
    96 static long bytes_in;   /* number of input bytes */
    97 
    98 #define isize bytes_in
    99 /* for compatibility with old zip sources (to be cleaned) */
    100 
    101 typedef int file_t;     /* Do not use stdio */
    102 
    103 #define NO_FILE  (-1)   /* in memory compression */
    104 
    105 
    106 #define PACK_MAGIC     "\037\036"   /* Magic header for packed files */
    107 #define GZIP_MAGIC     "\037\213"   /* Magic header for gzip files, 1F 8B */
    108 #define OLD_GZIP_MAGIC "\037\236"   /* Magic header for gzip 0.5 = freeze 1.x */
    109 #define LZH_MAGIC      "\037\240"   /* Magic header for SCO LZH Compress files */
    110 #define PKZIP_MAGIC    "\120\113\003\004"   /* Magic header for pkzip files */
    11193
    11294/* gzip flag byte */
    … …  
    124106
    125107#ifndef WSIZE
    126 #  define WSIZE 0x8000  /* window size--must be a power of two, and */
    127 #endif                          /*  at least 32K for zip's deflate method */
     108#  define WSIZE 0x8000  /* window size--must be a power of two, and */
     109#endif                  /*  at least 32K for zip's deflate method */
    128110
    129111#define MIN_MATCH  3
    … …  
    141123 */
    142124
    143 /* put_byte is used for the compressed output */
    144 #define put_byte(c) {outbuf[outcnt++]=(uch)(c); if (outcnt==OUTBUFSIZ)\
    145    flush_outbuf();}
    146 
    147 
    148 /* Output a 32 bit value to the bit stream, lsb first */
    149 #if 0
    150 #define put_long(n) { \
    151     put_short((n) & 0xffff); \
    152     put_short(((ulg)(n)) >> 16); \
    153 }
     125#ifndef MAX_PATH_LEN
     126#  define MAX_PATH_LEN   1024   /* max pathname length */
    154127#endif
    155128
    156129#define seekable()    0 /* force sequential output */
    157130#define translate_eol 0 /* no option -a yet */
    158 
    159 /* Diagnostic functions */
    160 #ifdef DEBUG
    161 #  define Assert(cond,msg) {if(!(cond)) bb_error_msg(msg);}
    162 #  define Trace(x) fprintf x
    163 #  define Tracev(x) {if (verbose) fprintf x ;}
    164 #  define Tracevv(x) {if (verbose>1) fprintf x ;}
    165 #  define Tracec(c,x) {if (verbose && (c)) fprintf x ;}
    166 #  define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;}
    167 #else
    168 #  define Assert(cond,msg)
    169 #  define Trace(x)
    170 #  define Tracev(x)
    171 #  define Tracevv(x)
    172 #  define Tracec(c,x)
    173 #  define Tracecv(c,x)
    174 #endif
    175 
    176 #define WARN(msg) {if (!quiet) fprintf msg ; \
    177            if (exit_code == OK) exit_code = WARNING;}
    178 
    179 #ifndef MAX_PATH_LEN
    180 #  define MAX_PATH_LEN   1024   /* max pathname length */
    181 #endif
    182 
    183 
    184     /* from zip.c: */
    185 static int zip(int in, int out);
    186 static int file_read(char *buf, unsigned size);
    187 
    188         /* from deflate.c */
    189 static void lm_init(ush * flags);
    190 static ulg deflate(void);
    191 
    192         /* from trees.c */
    193 static void ct_init(ush * attr, int *methodp);
    194 static int ct_tally(int dist, int lc);
    195 static ulg flush_block(char *buf, ulg stored_len, int eof);
    196 
    197         /* from bits.c */
    198 static void bi_init(file_t zipfile);
    199 static void send_bits(int value, int length);
    200 static unsigned bi_reverse(unsigned value, int length);
    201 static void bi_windup(void);
    202 static void copy_block(char *buf, unsigned len, int header);
    203 static int (*read_buf) (char *buf, unsigned size);
    204 
    205     /* from util.c: */
    206 static void flush_outbuf(void);
    207 
    208 /* lzw.h -- define the lzw functions.
    209  * Copyright (C) 1992-1993 Jean-loup Gailly.
    210  * This is free software; you can redistribute it and/or modify it under the
    211  * terms of the GNU General Public License, see the file COPYING.
    212  */
    213131
    214132#ifndef BITS
    … …  
    227145 */
    228146
    229 /* tailor.h -- target dependent definitions
    230  * Copyright (C) 1992-1993 Jean-loup Gailly.
    231  * This is free software; you can redistribute it and/or modify it under the
    232  * terms of the GNU General Public License, see the file COPYING.
    233  */
    234 
    235 /* The target dependent definitions should be defined here only.
    236  * The target dependent functions should be defined in tailor.c.
    237  */
    238 
    239 
    240     /* Common defaults */
    241 
    242 #ifndef OS_CODE
    243 #  define OS_CODE  0x03 /* assume Unix */
    244 #endif
    245 
    246 #ifndef PATH_SEP
    247 #  define PATH_SEP '/'
    248 #endif
    249 
    250 #ifndef OPTIONS_VAR
    251 #  define OPTIONS_VAR "GZIP"
    252 #endif
    253 
    254 #ifndef Z_SUFFIX
    255 #  define Z_SUFFIX ".gz"
    256 #endif
    257 
    258147#ifdef MAX_EXT_CHARS
    259148#  define MAX_SUFFIX  MAX_EXT_CHARS
    … …  
    262151#endif
    263152
    264         /* global buffers */
    265 
    266 DECLARE(uch, inbuf, INBUFSIZ + INBUF_EXTRA);
    267 DECLARE(uch, outbuf, OUTBUFSIZ + OUTBUF_EXTRA);
    268 DECLARE(ush, d_buf, DIST_BUFSIZE);
    269 DECLARE(uch, window, 2L * WSIZE);
    270 DECLARE(ush, tab_prefix, 1L << BITS);
    271 
    272 static int foreground;  /* set if program run in foreground */
    273 static int method = DEFLATED;   /* compression method */
    274 static int exit_code = OK;  /* program exit code */
    275 static int part_nb;     /* number of parts in .gz file */
    276 static long time_stamp; /* original time stamp (modification time) */
    277 static long ifile_size; /* input file size, -1 for devices (debug only) */
    278 static char z_suffix[MAX_SUFFIX + 1];   /* default suffix (can be set with --suffix) */
    279 static int z_len;       /* strlen(z_suffix) */
    280 
    281 static int ifd;         /* input file descriptor */
    282 static int ofd;         /* output file descriptor */
    283 static unsigned insize; /* valid bytes in inbuf */
    284 static unsigned outcnt; /* bytes in output buffer */
    285 
    286 static uint32_t *crc_32_tab;
    287 
    288 /* Output a 16 bit value, lsb first */
    289 static void put_short(ush w)
    290 {
    291     if (outcnt < OUTBUFSIZ - 2) {
    292         outbuf[outcnt++] = (uch) ((w) & 0xff);
    293         outbuf[outcnt++] = (uch) ((ush) (w) >> 8);
    294     } else {
    295         put_byte((uch) ((w) & 0xff));
    296         put_byte((uch) ((ush) (w) >> 8));
    297     }
    298 }
    299 
    300 /* ========================================================================
    301  * Signal and error handler.
    302  */
    303 static void abort_gzip(int ATTRIBUTE_UNUSED ignored)
    304 {
    305     exit(ERROR);
    306 }
    307 
    308 /* ===========================================================================
    309  * Clear input and output buffers
    310  */
    311 static void clear_bufs(void)
    312 {
    313     outcnt = 0;
    314     insize = 0;
    315     bytes_in = 0L;
    316 }
    317 
    318 /* ===========================================================================
    319  * Does the same as write(), but also handles partial pipe writes and checks
    320  * for error return.
    321  */
    322 static void write_buf(int fd, void *buf, unsigned cnt)
    323 {
    324     unsigned n;
    325 
    326     while ((n = write(fd, buf, cnt)) != cnt) {
    327         if (n == (unsigned) (-1)) bb_error_msg_and_die(bb_msg_write_error);
    328         cnt -= n;
    329         buf = (void *) ((char *) buf + n);
    330     }
    331 }
    332 
    333 /* ===========================================================================
    334  * Run a set of bytes through the crc shift register.  If s is a NULL
    335  * pointer, then initialize the crc shift register contents instead.
    336  * Return the current crc in either case.
    337  */
    338 static uint32_t updcrc(uch * s, unsigned n)
    339 {
    340     static uint32_t crc = ~0;   /* shift register contents */
    341     uint32_t c;     /* temporary variable */
    342 
    343     if (s == NULL) {
    344         c = ~0;
    345     } else {
    346         c = crc;
    347         if (n)
    348             do {
    349                 c = crc_32_tab[((int) c ^ (*s++)) & 0xff] ^ (c >> 8);
    350             } while (--n);
    351     }
    352     crc = c;
    353     return ~c;
    354 }
    355 
    356 /* bits.c -- output variable-length bit strings
    357  * Copyright (C) 1992-1993 Jean-loup Gailly
    358  * This is free software; you can redistribute it and/or modify it under the
    359  * terms of the GNU General Public License, see the file COPYING.
    360  */
    361 
    362 
    363 /*
    364  *  PURPOSE
    365  *
    366  *      Output variable-length bit strings. Compression can be done
    367  *      to a file or to memory. (The latter is not supported in this version.)
    368  *
    369  *  DISCUSSION
    370  *
    371  *      The PKZIP "deflate" file format interprets compressed file data
    372  *      as a sequence of bits.  Multi-bit strings in the file may cross
    373  *      byte boundaries without restriction.
    374  *
    375  *      The first bit of each byte is the low-order bit.
    376  *
    377  *      The routines in this file allow a variable-length bit value to
    378  *      be output right-to-left (useful for literal values). For
    379  *      left-to-right output (useful for code strings from the tree routines),
    380  *      the bits must have been reversed first with bi_reverse().
    381  *
    382  *      For in-memory compression, the compressed bit stream goes directly
    383  *      into the requested output buffer. The input data is read in blocks
    384  *      by the mem_read() function. The buffer is limited to 64K on 16 bit
    385  *      machines.
    386  *
    387  *  INTERFACE
    388  *
    389  *      void bi_init (FILE *zipfile)
    390  *          Initialize the bit string routines.
    391  *
    392  *      void send_bits (int value, int length)
    393  *          Write out a bit string, taking the source bits right to
    394  *          left.
    395  *
    396  *      int bi_reverse (int value, int length)
    397  *          Reverse the bits of a bit string, taking the source bits left to
    398  *          right and emitting them right to left.
    399  *
    400  *      void bi_windup (void)
    401  *          Write out any remaining bits in an incomplete byte.
    402  *
    403  *      void copy_block(char *buf, unsigned len, int header)
    404  *          Copy a stored block to the zip file, storing first the length and
    405  *          its one's complement if requested.
    406  *
    407  */
    408 
    409 /* ===========================================================================
    410  * Local data used by the "bit string" routines.
    411  */
    412 
    413 static file_t zfile;    /* output gzip file */
    414 
    415 static unsigned short bi_buf;
    416 
    417 /* Output buffer. bits are inserted starting at the bottom (least significant
    418  * bits).
    419  */
    420 
    421 #define Buf_size (8 * 2*sizeof(char))
    422 /* Number of bits used within bi_buf. (bi_buf might be implemented on
    423  * more than 16 bits on some systems.)
    424  */
    425 
    426 static int bi_valid;
    427 
    428 /* Current input function. Set to mem_read for in-memory compression */
    429 
    430 #ifdef DEBUG
    431 ulg bits_sent;          /* bit length of the compressed data */
    432 #endif
    433 
    434 /* ===========================================================================
    435  * Initialize the bit string routines.
    436  */
    437 static void bi_init(file_t zipfile)
    438 {
    439     zfile = zipfile;
    440     bi_buf = 0;
    441     bi_valid = 0;
    442 #ifdef DEBUG
    443     bits_sent = 0L;
    444 #endif
    445 
    446     /* Set the defaults for file compression. They are set by memcompress
    447      * for in-memory compression.
    448      */
    449     if (zfile != NO_FILE) {
    450         read_buf = file_read;
    451     }
    452 }
    453 
    454 /* ===========================================================================
    455  * Send a value on a given number of bits.
    456  * IN assertion: length <= 16 and value fits in length bits.
    457  */
    458 static void send_bits(int value, int length)
    459 {
    460 #ifdef DEBUG
    461     Tracev((stderr, " l %2d v %4x ", length, value));
    462     Assert(length > 0 && length <= 15, "invalid length");
    463     bits_sent += (ulg) length;
    464 #endif
    465     /* If not enough room in bi_buf, use (valid) bits from bi_buf and
    466      * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
    467      * unused bits in value.
    468      */
    469     if (bi_valid > (int) Buf_size - length) {
    470         bi_buf |= (value << bi_valid);
    471         put_short(bi_buf);
    472         bi_buf = (ush) value >> (Buf_size - bi_valid);
    473         bi_valid += length - Buf_size;
    474     } else {
    475         bi_buf |= value << bi_valid;
    476         bi_valid += length;
    477     }
    478 }
    479 
    480 /* ===========================================================================
    481  * Reverse the first len bits of a code, using straightforward code (a faster
    482  * method would use a table)
    483  * IN assertion: 1 <= len <= 15
    484  */
    485 static unsigned bi_reverse(unsigned code, int len)
    486 {
    487     register unsigned res = 0;
    488 
    489     do {
    490         res |= code & 1;
    491         code >>= 1, res <<= 1;
    492     } while (--len > 0);
    493     return res >> 1;
    494 }
    495 
    496 /* ===========================================================================
    497  * Write out any remaining bits in an incomplete byte.
    498  */
    499 static void bi_windup(void)
    500 {
    501     if (bi_valid > 8) {
    502         put_short(bi_buf);
    503     } else if (bi_valid > 0) {
    504         put_byte(bi_buf);
    505     }
    506     bi_buf = 0;
    507     bi_valid = 0;
    508 #ifdef DEBUG
    509     bits_sent = (bits_sent + 7) & ~7;
    510 #endif
    511 }
    512 
    513 /* ===========================================================================
    514  * Copy a stored block to the zip file, storing first the length and its
    515  * one's complement if requested.
    516  */
    517 static void copy_block(char *buf, unsigned len, int header)
    518 {
    519     bi_windup();        /* align on byte boundary */
    520 
    521     if (header) {
    522         put_short((ush) len);
    523         put_short((ush) ~ len);
    524 #ifdef DEBUG
    525         bits_sent += 2 * 16;
    526 #endif
    527     }
    528 #ifdef DEBUG
    529     bits_sent += (ulg) len << 3;
    530 #endif
    531     while (len--) {
    532         put_byte(*buf++);
    533     }
    534 }
    535 
    536 /* deflate.c -- compress data using the deflation algorithm
    537  * Copyright (C) 1992-1993 Jean-loup Gailly
    538  * This is free software; you can redistribute it and/or modify it under the
    539  * terms of the GNU General Public License, see the file COPYING.
    540  */
    541 
    542 /*
    543  *  PURPOSE
    544  *
    545  *      Identify new text as repetitions of old text within a fixed-
    546  *      length sliding window trailing behind the new text.
    547  *
    548  *  DISCUSSION
    549  *
    550  *      The "deflation" process depends on being able to identify portions
    551  *      of the input text which are identical to earlier input (within a
    552  *      sliding window trailing behind the input currently being processed).
    553  *
    554  *      The most straightforward technique turns out to be the fastest for
    555  *      most input files: try all possible matches and select the longest.
    556  *      The key feature of this algorithm is that insertions into the string
    557  *      dictionary are very simple and thus fast, and deletions are avoided
    558  *      completely. Insertions are performed at each input character, whereas
    559  *      string matches are performed only when the previous match ends. So it
    560  *      is preferable to spend more time in matches to allow very fast string
    561  *      insertions and avoid deletions. The matching algorithm for small
    562  *      strings is inspired from that of Rabin & Karp. A brute force approach
    563  *      is used to find longer strings when a small match has been found.
    564  *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
    565  *      (by Leonid Broukhis).
    566  *         A previous version of this file used a more sophisticated algorithm
    567  *      (by Fiala and Greene) which is guaranteed to run in linear amortized
    568  *      time, but has a larger average cost, uses more memory and is patented.
    569  *      However the F&G algorithm may be faster for some highly redundant
    570  *      files if the parameter max_chain_length (described below) is too large.
    571  *
    572  *  ACKNOWLEDGMENTS
    573  *
    574  *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
    575  *      I found it in 'freeze' written by Leonid Broukhis.
    576  *      Thanks to many info-zippers for bug reports and testing.
    577  *
    578  *  REFERENCES
    579  *
    580  *      APPNOTE.TXT documentation file in PKZIP 1.93a distribution.
    581  *
    582  *      A description of the Rabin and Karp algorithm is given in the book
    583  *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
    584  *
    585  *      Fiala,E.R., and Greene,D.H.
    586  *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
    587  *
    588  *  INTERFACE
    589  *
    590  *      void lm_init (int pack_level, ush *flags)
    591  *          Initialize the "longest match" routines for a new file
    592  *
    593  *      ulg deflate (void)
    594  *          Processes a new input file and return its compressed length. Sets
    595  *          the compressed length, crc, deflate flags and internal file
    596  *          attributes.
    597  */
    598 
    599 
    600 /* ===========================================================================
    601  * Configuration parameters
    602  */
    603 
    604 /* Compile with MEDIUM_MEM to reduce the memory requirements or
     153
     154/* ===========================================================================
     155 * Compile with MEDIUM_MEM to reduce the memory requirements or
    605156 * with SMALL_MEM to use as little memory as possible. Use BIG_MEM if the
    606157 * entire input file can be held in memory (not possible on 16 bit systems).
    … …  
    621172#endif
    622173
    623 /* To save space (see unlzw.c), we overlay prev+head with tab_prefix and
    624  * window with tab_suffix. Check that we can do this:
    625  */
    626 #if (WSIZE<<1) > (1<<BITS)
    627 #  error cannot overlay window with tab_suffix and prev with tab_prefix0
    628 #endif
    629 #if HASH_BITS > BITS-1
    630 #  error cannot overlay head with tab_prefix1
    631 #endif
    632174#define HASH_SIZE (unsigned)(1<<HASH_BITS)
    633175#define HASH_MASK (HASH_SIZE-1)
    634176#define WMASK     (WSIZE-1)
    635177/* HASH_SIZE and WSIZE must be powers of two */
    636 #define NIL 0
    637 /* Tail of hash chains */
    638 #define FAST 4
    639 #define SLOW 2
    640 /* speed options for the general purpose bit flag */
    641178#ifndef TOO_FAR
    642179#  define TOO_FAR 4096
    643180#endif
    644181/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
    645 /* ===========================================================================
    646  * Local data used by the "longest match" routines.
    647  */
     182
     183
     184/* ===========================================================================
     185 * These types are not really 'char', 'short' and 'long'
     186 */
     187typedef uint8_t uch;
     188typedef uint16_t ush;
     189typedef uint32_t ulg;
     190typedef int32_t lng;
     191
    648192typedef ush Pos;
    649193typedef unsigned IPos;
    650 
    651194/* A Pos is an index in the character window. We use short instead of int to
    652195 * save space in the various tables. IPos is used only for parameter passing.
    653196 */
    654197
    655 /* DECLARE(uch, window, 2L*WSIZE); */
     198enum {
     199    WINDOW_SIZE = 2 * WSIZE,
     200/* window size, 2*WSIZE except for MMAP or BIG_MEM, where it is the
     201 * input file length plus MIN_LOOKAHEAD.
     202 */
     203
     204    max_chain_length = 4096,
     205/* To speed up deflation, hash chains are never searched beyond this length.
     206 * A higher limit improves compression ratio but degrades the speed.
     207 */
     208
     209    max_lazy_match = 258,
     210/* Attempt to find a better match only when the current match is strictly
     211 * smaller than this value. This mechanism is used only for compression
     212 * levels >= 4.
     213 */
     214
     215    max_insert_length = max_lazy_match,
     216/* Insert new strings in the hash table only if the match length
     217 * is not greater than this length. This saves time but degrades compression.
     218 * max_insert_length is used only for compression levels <= 3.
     219 */
     220
     221    good_match = 32,
     222/* Use a faster search when the previous match is longer than this */
     223
     224/* Values for max_lazy_match, good_match and max_chain_length, depending on
     225 * the desired pack level (0..9). The values given below have been tuned to
     226 * exclude worst case performance for pathological files. Better values may be
     227 * found for specific files.
     228 */
     229
     230    nice_match = 258,   /* Stop searching when current match exceeds this */
     231/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
     232 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
     233 * meaning.
     234 */
     235};
     236
     237
     238struct globals {
     239
     240    lng block_start;
     241
     242/* window position at the beginning of the current output block. Gets
     243 * negative when the window is moved backwards.
     244 */
     245    unsigned ins_h; /* hash index of string to be inserted */
     246
     247#define H_SHIFT  ((HASH_BITS+MIN_MATCH-1) / MIN_MATCH)
     248/* Number of bits by which ins_h and del_h must be shifted at each
     249 * input step. It must be such that after MIN_MATCH steps, the oldest
     250 * byte no longer takes part in the hash key, that is:
     251 * H_SHIFT * MIN_MATCH >= HASH_BITS
     252 */
     253
     254    unsigned prev_length;
     255
     256/* Length of the best match at previous step. Matches not greater than this
     257 * are discarded. This is used in the lazy match evaluation.
     258 */
     259
     260    unsigned strstart;  /* start of string to insert */
     261    unsigned match_start;   /* start of matching string */
     262    unsigned lookahead; /* number of valid bytes ahead in window */
     263
     264/* ===========================================================================
     265 */
     266#define DECLARE(type, array, size) \
     267    type * array
     268#define ALLOC(type, array, size) \
     269    array = xzalloc((size_t)(((size)+1L)/2) * 2*sizeof(type));
     270#define FREE(array) \
     271    do { free(array); array = NULL; } while (0)
     272
     273    /* global buffers */
     274
     275    /* buffer for literals or lengths */
     276    /* DECLARE(uch, l_buf, LIT_BUFSIZE); */
     277    DECLARE(uch, l_buf, INBUFSIZ);
     278
     279    DECLARE(ush, d_buf, DIST_BUFSIZE);
     280    DECLARE(uch, outbuf, OUTBUFSIZ);
     281
    656282/* Sliding window. Input bytes are read into the second half of the window,
    657283 * and move to the first half later to keep a dictionary of at least WSIZE
    … …  
    663289 * be less efficient).
    664290 */
    665 
    666 /* DECLARE(Pos, prev, WSIZE); */
     291    DECLARE(uch, window, 2L * WSIZE);
     292
    667293/* Link to older string with same hash index. To limit the size of this
    668294 * array to 64K, this link is maintained only for the last 32K strings.
    669295 * An index in this array is thus a window index modulo 32K.
    670296 */
    671 
    672 /* DECLARE(Pos, head, 1<<HASH_BITS); */
    673 /* Heads of the hash chains or NIL. */
    674 
    675 static const ulg window_size = (ulg) 2 * WSIZE;
    676 
    677 /* window size, 2*WSIZE except for MMAP or BIG_MEM, where it is the
    678  * input file length plus MIN_LOOKAHEAD.
    679  */
    680 
    681 static long block_start;
    682 
    683 /* window position at the beginning of the current output block. Gets
    684  * negative when the window is moved backwards.
    685  */
    686 
    687 static unsigned ins_h;  /* hash index of string to be inserted */
    688 
    689 #define H_SHIFT  ((HASH_BITS+MIN_MATCH-1)/MIN_MATCH)
    690 /* Number of bits by which ins_h and del_h must be shifted at each
    691  * input step. It must be such that after MIN_MATCH steps, the oldest
    692  * byte no longer takes part in the hash key, that is:
    693  *   H_SHIFT * MIN_MATCH >= HASH_BITS
    694  */
    695 
    696 static unsigned int prev_length;
    697 
    698 /* Length of the best match at previous step. Matches not greater than this
    699  * are discarded. This is used in the lazy match evaluation.
    700  */
    701 
    702 static unsigned strstart;   /* start of string to insert */
    703 static unsigned match_start;    /* start of matching string */
    704 static int eofile;      /* flag set at end of input file */
    705 static unsigned lookahead;  /* number of valid bytes ahead in window */
    706 
    707 enum {
    708     max_chain_length = 4096,
    709 
    710 /* To speed up deflation, hash chains are never searched beyond this length.
    711  * A higher limit improves compression ratio but degrades the speed.
    712  */
    713 
    714     max_lazy_match = 258,
    715 
    716 /* Attempt to find a better match only when the current match is strictly
    717  * smaller than this value. This mechanism is used only for compression
    718  * levels >= 4.
    719  */
    720     max_insert_length = max_lazy_match,
    721 /* Insert new strings in the hash table only if the match length
    722  * is not greater than this length. This saves time but degrades compression.
    723  * max_insert_length is used only for compression levels <= 3.
    724  */
    725 
    726     good_match = 32,
    727 
    728 /* Use a faster search when the previous match is longer than this */
    729 
    730 
    731 /* Values for max_lazy_match, good_match and max_chain_length, depending on
    732  * the desired pack level (0..9). The values given below have been tuned to
    733  * exclude worst case performance for pathological files. Better values may be
    734  * found for specific files.
    735  */
    736 
    737     nice_match = 258    /* Stop searching when current match exceeds this */
    738 
    739 /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
    740  * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
    741  * meaning.
    742  */
     297    /* DECLARE(Pos, prev, WSIZE); */
     298    DECLARE(ush, prev, 1L << BITS);
     299
     300/* Heads of the hash chains or 0. */
     301    /* DECLARE(Pos, head, 1<<HASH_BITS); */
     302#define head (G1.prev + WSIZE) /* hash head (see deflate.c) */
     303
     304/* number of input bytes */
     305    ulg isize;      /* only 32 bits stored in .gz file */
     306
     307/* bbox always use stdin/stdout */
     308#define ifd STDIN_FILENO    /* input file descriptor */
     309#define ofd STDOUT_FILENO   /* output file descriptor */
     310
     311#ifdef DEBUG
     312    unsigned insize;    /* valid bytes in l_buf */
     313#endif
     314    unsigned outcnt;    /* bytes in output buffer */
     315
     316    smallint eofile;    /* flag set at end of input file */
     317
     318/* ===========================================================================
     319 * Local data used by the "bit string" routines.
     320 */
     321
     322    unsigned short bi_buf;
     323
     324/* Output buffer. bits are inserted starting at the bottom (least significant
     325 * bits).
     326 */
     327
     328#undef BUF_SIZE
     329#define BUF_SIZE (8 * sizeof(G1.bi_buf))
     330/* Number of bits used within bi_buf. (bi_buf might be implemented on
     331 * more than 16 bits on some systems.)
     332 */
     333
     334    int bi_valid;
     335
     336/* Current input function. Set to mem_read for in-memory compression */
     337
     338#ifdef DEBUG
     339    ulg bits_sent;          /* bit length of the compressed data */
     340#endif
     341
     342    uint32_t *crc_32_tab;
     343    uint32_t crc;   /* shift register contents */
    743344};
    744345
    745 #define EQUAL 0
    746 /* result of memcmp for equal strings */
    747 
    748 /* ===========================================================================
    749  *  Prototypes for local functions.
    750  */
    751 static void fill_window(void);
    752 
    753 static int longest_match(IPos cur_match);
    754 
     346#define G1 (*(ptr_to_globals - 1))
     347
     348
     349/* ===========================================================================
     350 * Write the output buffer outbuf[0..outcnt-1] and update bytes_out.
     351 * (used for the compressed data only)
     352 */
     353static void flush_outbuf(void)
     354{
     355    if (G1.outcnt == 0)
     356        return;
     357
     358    xwrite(ofd, (char *) G1.outbuf, G1.outcnt);
     359    G1.outcnt = 0;
     360}
     361
     362
     363/* ===========================================================================
     364 */
     365/* put_8bit is used for the compressed output */
     366#define put_8bit(c) \
     367do { \
     368    G1.outbuf[G1.outcnt++] = (c); \
     369    if (G1.outcnt == OUTBUFSIZ) flush_outbuf(); \
     370} while (0)
     371
     372/* Output a 16 bit value, lsb first */
     373static void put_16bit(ush w)
     374{
     375    if (G1.outcnt < OUTBUFSIZ - 2) {
     376        G1.outbuf[G1.outcnt++] = w;
     377        G1.outbuf[G1.outcnt++] = w >> 8;
     378    } else {
     379        put_8bit(w);
     380        put_8bit(w >> 8);
     381    }
     382}
     383
     384static void put_32bit(ulg n)
     385{
     386    put_16bit(n);
     387    put_16bit(n >> 16);
     388}
     389
     390/* ===========================================================================
     391 * Clear input and output buffers
     392 */
     393static void clear_bufs(void)
     394{
     395    G1.outcnt = 0;
    755396#ifdef DEBUG
    756 static void check_match(IPos start, IPos match, int length);
    757 #endif
    758 
    759 /* ===========================================================================
    760  * Update a hash value with the given input byte
    761  * IN  assertion: all calls to to UPDATE_HASH are made with consecutive
    762  *    input characters, so that a running hash key can be computed from the
    763  *    previous key instead of complete recalculation each time.
    764  */
    765 #define UPDATE_HASH(h,c) (h = (((h)<<H_SHIFT) ^ (c)) & HASH_MASK)
    766 
    767 /* ===========================================================================
    768  * Insert string s in the dictionary and set match_head to the previous head
    769  * of the hash chain (the most recent string with same hash key). Return
    770  * the previous length of the hash chain.
    771  * IN  assertion: all calls to to INSERT_STRING are made with consecutive
    772  *    input characters and the first MIN_MATCH bytes of s are valid
    773  *    (except for the last MIN_MATCH-1 bytes of the input file).
    774  */
    775 #define INSERT_STRING(s, match_head) \
    776    (UPDATE_HASH(ins_h, window[(s) + MIN_MATCH-1]), \
    777     prev[(s) & WMASK] = match_head = head[ins_h], \
    778     head[ins_h] = (s))
    779 
    780 /* ===========================================================================
    781  * Initialize the "longest match" routines for a new file
    782  */
    783 static void lm_init(ush * flags)
    784 {
    785     register unsigned j;
    786 
    787     /* Initialize the hash table. */
    788     memset(head, 0, HASH_SIZE * sizeof(*head));
    789     /* prev will be initialized on the fly */
    790 
    791     *flags |= SLOW;
    792     /* ??? reduce max_chain_length for binary files */
    793 
    794     strstart = 0;
    795     block_start = 0L;
    796 
    797     lookahead = read_buf((char *) window,
    798                          sizeof(int) <= 2 ? (unsigned) WSIZE : 2 * WSIZE);
    799 
    800     if (lookahead == 0 || lookahead == (unsigned) EOF) {
    801         eofile = 1, lookahead = 0;
    802         return;
    803     }
    804     eofile = 0;
    805     /* Make sure that we always have enough lookahead. This is important
    806      * if input comes from a device such as a tty.
    807      */
    808     while (lookahead < MIN_LOOKAHEAD && !eofile)
    809         fill_window();
    810 
    811     ins_h = 0;
    812     for (j = 0; j < MIN_MATCH - 1; j++)
    813         UPDATE_HASH(ins_h, window[j]);
    814     /* If lookahead < MIN_MATCH, ins_h is garbage, but this is
    815      * not important since only literal bytes will be emitted.
    816      */
    817 }
     397    G1.insize = 0;
     398#endif
     399    G1.isize = 0;
     400}
     401
     402
     403/* ===========================================================================
     404 * Run a set of bytes through the crc shift register.  If s is a NULL
     405 * pointer, then initialize the crc shift register contents instead.
     406 * Return the current crc in either case.
     407 */
     408static uint32_t updcrc(uch * s, unsigned n)
     409{
     410    uint32_t c = G1.crc;
     411    while (n) {
     412        c = G1.crc_32_tab[(uch)(c ^ *s++)] ^ (c >> 8);
     413        n--;
     414    }
     415    G1.crc = c;
     416    return c;
     417}
     418
     419
     420/* ===========================================================================
     421 * Read a new buffer from the current input file, perform end-of-line
     422 * translation, and update the crc and input file size.
     423 * IN assertion: size >= 2 (for end-of-line translation)
     424 */
     425static unsigned file_read(void *buf, unsigned size)
     426{
     427    unsigned len;
     428
     429    Assert(G1.insize == 0, "l_buf not empty");
     430
     431    len = safe_read(ifd, buf, size);
     432    if (len == (unsigned)(-1) || len == 0)
     433        return len;
     434
     435    updcrc(buf, len);
     436    G1.isize += len;
     437    return len;
     438}
     439
     440
     441/* ===========================================================================
     442 * Send a value on a given number of bits.
     443 * IN assertion: length <= 16 and value fits in length bits.
     444 */
     445static void send_bits(int value, int length)
     446{
     447#ifdef DEBUG
     448    Tracev((stderr, " l %2d v %4x ", length, value));
     449    Assert(length > 0 && length <= 15, "invalid length");
     450    G1.bits_sent += length;
     451#endif
     452    /* If not enough room in bi_buf, use (valid) bits from bi_buf and
     453     * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
     454     * unused bits in value.
     455     */
     456    if (G1.bi_valid > (int) BUF_SIZE - length) {
     457        G1.bi_buf |= (value << G1.bi_valid);
     458        put_16bit(G1.bi_buf);
     459        G1.bi_buf = (ush) value >> (BUF_SIZE - G1.bi_valid);
     460        G1.bi_valid += length - BUF_SIZE;
     461    } else {
     462        G1.bi_buf |= value << G1.bi_valid;
     463        G1.bi_valid += length;
     464    }
     465}
     466
     467
     468/* ===========================================================================
     469 * Reverse the first len bits of a code, using straightforward code (a faster
     470 * method would use a table)
     471 * IN assertion: 1 <= len <= 15
     472 */
     473static unsigned bi_reverse(unsigned code, int len)
     474{
     475    unsigned res = 0;
     476
     477    while (1) {
     478        res |= code & 1;
     479        if (--len <= 0) return res;
     480        code >>= 1;
     481        res <<= 1;
     482    }
     483}
     484
     485
     486/* ===========================================================================
     487 * Write out any remaining bits in an incomplete byte.
     488 */
     489static void bi_windup(void)
     490{
     491    if (G1.bi_valid > 8) {
     492        put_16bit(G1.bi_buf);
     493    } else if (G1.bi_valid > 0) {
     494        put_8bit(G1.bi_buf);
     495    }
     496    G1.bi_buf = 0;
     497    G1.bi_valid = 0;
     498#ifdef DEBUG
     499    G1.bits_sent = (G1.bits_sent + 7) & ~7;
     500#endif
     501}
     502
     503
     504/* ===========================================================================
     505 * Copy a stored block to the zip file, storing first the length and its
     506 * one's complement if requested.
     507 */
     508static void copy_block(char *buf, unsigned len, int header)
     509{
     510    bi_windup();        /* align on byte boundary */
     511
     512    if (header) {
     513        put_16bit(len);
     514        put_16bit(~len);
     515#ifdef DEBUG
     516        G1.bits_sent += 2 * 16;
     517#endif
     518    }
     519#ifdef DEBUG
     520    G1.bits_sent += (ulg) len << 3;
     521#endif
     522    while (len--) {
     523        put_8bit(*buf++);
     524    }
     525}
     526
     527
     528/* ===========================================================================
     529 * Fill the window when the lookahead becomes insufficient.
     530 * Updates strstart and lookahead, and sets eofile if end of input file.
     531 * IN assertion: lookahead < MIN_LOOKAHEAD && strstart + lookahead > 0
     532 * OUT assertions: at least one byte has been read, or eofile is set;
     533 *    file reads are performed for at least two bytes (required for the
     534 *    translate_eol option).
     535 */
     536static void fill_window(void)
     537{
     538    unsigned n, m;
     539    unsigned more = WINDOW_SIZE - G1.lookahead - G1.strstart;
     540    /* Amount of free space at the end of the window. */
     541
     542    /* If the window is almost full and there is insufficient lookahead,
     543     * move the upper half to the lower one to make room in the upper half.
     544     */
     545    if (more == (unsigned) -1) {
     546        /* Very unlikely, but possible on 16 bit machine if strstart == 0
     547         * and lookahead == 1 (input done one byte at time)
     548         */
     549        more--;
     550    } else if (G1.strstart >= WSIZE + MAX_DIST) {
     551        /* By the IN assertion, the window is not empty so we can't confuse
     552         * more == 0 with more == 64K on a 16 bit machine.
     553         */
     554        Assert(WINDOW_SIZE == 2 * WSIZE, "no sliding with BIG_MEM");
     555
     556        memcpy(G1.window, G1.window + WSIZE, WSIZE);
     557        G1.match_start -= WSIZE;
     558        G1.strstart -= WSIZE;   /* we now have strstart >= MAX_DIST: */
     559
     560        G1.block_start -= WSIZE;
     561
     562        for (n = 0; n < HASH_SIZE; n++) {
     563            m = head[n];
     564            head[n] = (Pos) (m >= WSIZE ? m - WSIZE : 0);
     565        }
     566        for (n = 0; n < WSIZE; n++) {
     567            m = G1.prev[n];
     568            G1.prev[n] = (Pos) (m >= WSIZE ? m - WSIZE : 0);
     569            /* If n is not on any hash chain, prev[n] is garbage but
     570             * its value will never be used.
     571             */
     572        }
     573        more += WSIZE;
     574    }
     575    /* At this point, more >= 2 */
     576    if (!G1.eofile) {
     577        n = file_read(G1.window + G1.strstart + G1.lookahead, more);
     578        if (n == 0 || n == (unsigned) -1) {
     579            G1.eofile = 1;
     580        } else {
     581            G1.lookahead += n;
     582        }
     583    }
     584}
     585
    818586
    819587/* ===========================================================================
    … …  
    833601{
    834602    unsigned chain_length = max_chain_length;   /* max hash chain length */
    835     register uch *scan = window + strstart; /* current string */
    836     register uch *match;    /* matched string */
    837     register int len;   /* length of current match */
    838     int best_len = prev_length; /* best match length so far */
    839     IPos limit =
    840         strstart > (IPos) MAX_DIST ? strstart - (IPos) MAX_DIST : NIL;
     603    uch *scan = G1.window + G1.strstart;    /* current string */
     604    uch *match; /* matched string */
     605    int len;    /* length of current match */
     606    int best_len = G1.prev_length;  /* best match length so far */
     607    IPos limit = G1.strstart > (IPos) MAX_DIST ? G1.strstart - (IPos) MAX_DIST : 0;
    841608    /* Stop when cur_match becomes <= limit. To simplify the code,
    842609     * we prevent matches with the string of window index 0.
    … …  
    849616#  error Code too clever
    850617#endif
    851     register uch *strend = window + strstart + MAX_MATCH;
    852     register uch scan_end1 = scan[best_len - 1];
    853     register uch scan_end = scan[best_len];
     618    uch *strend = G1.window + G1.strstart + MAX_MATCH;
     619    uch scan_end1 = scan[best_len - 1];
     620    uch scan_end = scan[best_len];
    854621
    855622    /* Do not waste too much time if we already have a good match: */
    856     if (prev_length >= good_match) {
     623    if (G1.prev_length >= good_match) {
    857624        chain_length >>= 2;
    858625    }
    859     Assert(strstart <= window_size - MIN_LOOKAHEAD, "insufficient lookahead");
     626    Assert(G1.strstart <= WINDOW_SIZE - MIN_LOOKAHEAD, "insufficient lookahead");
    860627
    861628    do {
    862         Assert(cur_match < strstart, "no future");
    863         match = window + cur_match;
     629        Assert(cur_match < G1.strstart, "no future");
     630        match = G1.window + cur_match;
    864631
    865632        /* Skip to next match if the match length cannot increase
    … …  
    892659
    893660        if (len > best_len) {
    894             match_start = cur_match;
     661            G1.match_start = cur_match;
    895662            best_len = len;
    896663            if (len >= nice_match)
    … …  
    899666            scan_end = scan[best_len];
    900667        }
    901     } while ((cur_match = prev[cur_match & WMASK]) > limit
     668    } while ((cur_match = G1.prev[cur_match & WMASK]) > limit
    902669             && --chain_length != 0);
    903670
    … …  
    905672}
    906673
     674
    907675#ifdef DEBUG
    908676/* ===========================================================================
    … …  
    912680{
    913681    /* check that the match is indeed a match */
    914     if (memcmp((char *) window + match,
    915                (char *) window + start, length) != EQUAL) {
     682    if (memcmp(G1.window + match, G1.window + start, length) != 0) {
    916683        bb_error_msg(" start %d, match %d, length %d", start, match, length);
    917684        bb_error_msg("invalid match");
    … …  
    920687        bb_error_msg("\\[%d,%d]", start - match, length);
    921688        do {
    922             putc(window[start++], stderr);
     689            putc(G1.window[start++], stderr);
    923690        } while (--length != 0);
    924691    }
    925692}
    926693#else
    927 #  define check_match(start, match, length)
    928 #endif
    929 
    930 /* ===========================================================================
    931  * Fill the window when the lookahead becomes insufficient.
    932  * Updates strstart and lookahead, and sets eofile if end of input file.
    933  * IN assertion: lookahead < MIN_LOOKAHEAD && strstart + lookahead > 0
    934  * OUT assertions: at least one byte has been read, or eofile is set;
    935  *    file reads are performed for at least two bytes (required for the
    936  *    translate_eol option).
    937  */
    938 static void fill_window(void)
    939 {
    940     register unsigned n, m;
    941     unsigned more =
    942         (unsigned) (window_size - (ulg) lookahead - (ulg) strstart);
    943     /* Amount of free space at the end of the window. */
    944 
    945     /* If the window is almost full and there is insufficient lookahead,
    946      * move the upper half to the lower one to make room in the upper half.
    947      */
    948     if (more == (unsigned) EOF) {
    949         /* Very unlikely, but possible on 16 bit machine if strstart == 0
    950          * and lookahead == 1 (input done one byte at time)
    951          */
    952         more--;
    953     } else if (strstart >= WSIZE + MAX_DIST) {
    954         /* By the IN assertion, the window is not empty so we can't confuse
    955          * more == 0 with more == 64K on a 16 bit machine.
    956          */
    957         Assert(window_size == (ulg) 2 * WSIZE, "no sliding with BIG_MEM");
    958 
    959         memcpy((char *) window, (char *) window + WSIZE, (unsigned) WSIZE);
    960         match_start -= WSIZE;
    961         strstart -= WSIZE;  /* we now have strstart >= MAX_DIST: */
    962 
    963         block_start -= (long) WSIZE;
    964 
    965         for (n = 0; n < HASH_SIZE; n++) {
    966             m = head[n];
    967             head[n] = (Pos) (m >= WSIZE ? m - WSIZE : NIL);
    968         }
    969         for (n = 0; n < WSIZE; n++) {
    970             m = prev[n];
    971             prev[n] = (Pos) (m >= WSIZE ? m - WSIZE : NIL);
    972             /* If n is not on any hash chain, prev[n] is garbage but
    973              * its value will never be used.
    974              */
    975         }
    976         more += WSIZE;
    977     }
    978     /* At this point, more >= 2 */
    979     if (!eofile) {
    980         n = read_buf((char *) window + strstart + lookahead, more);
    981         if (n == 0 || n == (unsigned) EOF) {
    982             eofile = 1;
    983         } else {
    984             lookahead += n;
    985         }
    986     }
    987 }
    988 
    989 /* ===========================================================================
    990  * Flush the current block, with given end-of-file flag.
    991  * IN assertion: strstart is set to the end of the current match.
    992  */
    993 #define FLUSH_BLOCK(eof) \
    994    flush_block(block_start >= 0L ? (char*)&window[(unsigned)block_start] : \
    995         (char*)NULL, (long)strstart - block_start, (eof))
    996 
    997 /* ===========================================================================
    998  * Same as above, but achieves better compression. We use a lazy
    999  * evaluation for matches: a match is finally adopted only if there is
    1000  * no better match at the next window position.
    1001  */
    1002 static ulg deflate(void)
    1003 {
    1004     IPos hash_head;     /* head of hash chain */
    1005     IPos prev_match;    /* previous match */
    1006     int flush;          /* set if current block must be flushed */
    1007     int match_available = 0;    /* set if previous match exists */
    1008     register unsigned match_length = MIN_MATCH - 1; /* length of best match */
    1009 
    1010     /* Process the input block. */
    1011     while (lookahead != 0) {
    1012         /* Insert the string window[strstart .. strstart+2] in the
    1013          * dictionary, and set hash_head to the head of the hash chain:
    1014          */
    1015         INSERT_STRING(strstart, hash_head);
    1016 
    1017         /* Find the longest match, discarding those <= prev_length.
    1018          */
    1019         prev_length = match_length, prev_match = match_start;
    1020         match_length = MIN_MATCH - 1;
    1021 
    1022         if (hash_head != NIL && prev_length < max_lazy_match &&
    1023             strstart - hash_head <= MAX_DIST) {
    1024             /* To simplify the code, we prevent matches with the string
    1025              * of window index 0 (in particular we have to avoid a match
    1026              * of the string with itself at the start of the input file).
    1027              */
    1028             match_length = longest_match(hash_head);
    1029             /* longest_match() sets match_start */
    1030             if (match_length > lookahead)
    1031                 match_length = lookahead;
    1032 
    1033             /* Ignore a length 3 match if it is too distant: */
    1034             if (match_length == MIN_MATCH && strstart - match_start > TOO_FAR) {
    1035                 /* If prev_match is also MIN_MATCH, match_start is garbage
    1036                  * but we will ignore the current match anyway.
    1037                  */
    1038                 match_length--;
    1039             }
    1040         }
    1041         /* If there was a match at the previous step and the current
    1042          * match is not better, output the previous match:
    1043          */
    1044         if (prev_length >= MIN_MATCH && match_length <= prev_length) {
    1045 
    1046             check_match(strstart - 1, prev_match, prev_length);
    1047 
    1048             flush =
    1049                 ct_tally(strstart - 1 - prev_match, prev_length - MIN_MATCH);
    1050 
    1051             /* Insert in hash table all strings up to the end of the match.
    1052              * strstart-1 and strstart are already inserted.
    1053              */
    1054             lookahead -= prev_length - 1;
    1055             prev_length -= 2;
    1056             do {
    1057                 strstart++;
    1058                 INSERT_STRING(strstart, hash_head);
    1059                 /* strstart never exceeds WSIZE-MAX_MATCH, so there are
    1060                  * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
    1061                  * these bytes are garbage, but it does not matter since the
    1062                  * next lookahead bytes will always be emitted as literals.
    1063                  */
    1064             } while (--prev_length != 0);
    1065             match_available = 0;
    1066             match_length = MIN_MATCH - 1;
    1067             strstart++;
    1068             if (flush)
    1069                 FLUSH_BLOCK(0), block_start = strstart;
    1070 
    1071         } else if (match_available) {
    1072             /* If there was no match at the previous position, output a
    1073              * single literal. If there was a match but the current match
    1074              * is longer, truncate the previous match to a single literal.
    1075              */
    1076             Tracevv((stderr, "%c", window[strstart - 1]));
    1077             if (ct_tally(0, window[strstart - 1])) {
    1078                 FLUSH_BLOCK(0), block_start = strstart;
    1079             }
    1080             strstart++;
    1081             lookahead--;
    1082         } else {
    1083             /* There is no previous match to compare with, wait for
    1084              * the next step to decide.
    1085              */
    1086             match_available = 1;
    1087             strstart++;
    1088             lookahead--;
    1089         }
    1090         Assert(strstart <= isize && lookahead <= isize, "a bit too far");
    1091 
    1092         /* Make sure that we always have enough lookahead, except
    1093          * at the end of the input file. We need MAX_MATCH bytes
    1094          * for the next match, plus MIN_MATCH bytes to insert the
    1095          * string following the next match.
    1096          */
    1097         while (lookahead < MIN_LOOKAHEAD && !eofile)
    1098             fill_window();
    1099     }
    1100     if (match_available)
    1101         ct_tally(0, window[strstart - 1]);
    1102 
    1103     return FLUSH_BLOCK(1);  /* eof */
    1104 }
    1105 
    1106 /* gzip (GNU zip) -- compress files with zip algorithm and 'compress' interface
    1107  * Copyright (C) 1992-1993 Jean-loup Gailly
    1108  * The unzip code was written and put in the public domain by Mark Adler.
    1109  * Portions of the lzw code are derived from the public domain 'compress'
    1110  * written by Spencer Thomas, Joe Orost, James Woods, Jim McKie, Steve Davies,
    1111  * Ken Turkowski, Dave Mack and Peter Jannesen.
    1112  *
    1113  * See the license_msg below and the file COPYING for the software license.
    1114  * See the file algorithm.doc for the compression algorithms and file formats.
    1115  */
    1116 
    1117 /* Compress files with zip algorithm and 'compress' interface.
    1118  * See usage() and help() functions below for all options.
    1119  * Outputs:
    1120  *        file.gz:   compressed file with same mode, owner, and utimes
    1121  *     or stdout with -c option or if stdin used as input.
    1122  * If the output file name had to be truncated, the original name is kept
    1123  * in the compressed file.
    1124  */
    1125 
    1126         /* configuration */
    1127 
    1128 typedef struct dirent dir_type;
    1129 
    1130 /* ======================================================================== */
    1131 int gzip_main(int argc, char **argv)
    1132 {
    1133     int result;
    1134     int inFileNum;
    1135     int outFileNum;
    1136     struct stat statBuf;
    1137     char *delFileName;
    1138     int tostdout = 0;
    1139     int force = 0;
    1140     int opt;
    1141 
    1142     while ((opt = getopt(argc, argv, "cf123456789dq")) != -1) {
    1143         switch (opt) {
    1144         case 'c':
    1145             tostdout = 1;
    1146             break;
    1147         case 'f':
    1148             force = 1;
    1149             break;
    1150             /* Ignore 1-9 (compression level) options */
    1151         case '1':
    1152         case '2':
    1153         case '3':
    1154         case '4':
    1155         case '5':
    1156         case '6':
    1157         case '7':
    1158         case '8':
    1159         case '9':
    1160             break;
    1161         case 'q':
    1162             break;
    1163 #ifdef CONFIG_GUNZIP
    1164         case 'd':
    1165             optind = 1;
    1166             return gunzip_main(argc, argv);
    1167 #endif
    1168         default:
    1169             bb_show_usage();
    1170         }
    1171     }
    1172 
    1173     foreground = signal(SIGINT, SIG_IGN) != SIG_IGN;
    1174     if (foreground) {
    1175         (void) signal(SIGINT, abort_gzip);
    1176     }
    1177 #ifdef SIGTERM
    1178     if (signal(SIGTERM, SIG_IGN) != SIG_IGN) {
    1179         (void) signal(SIGTERM, abort_gzip);
    1180     }
    1181 #endif
    1182 #ifdef SIGHUP
    1183     if (signal(SIGHUP, SIG_IGN) != SIG_IGN) {
    1184         (void) signal(SIGHUP, abort_gzip);
    1185     }
    1186 #endif
    1187 
    1188     strncpy(z_suffix, Z_SUFFIX, sizeof(z_suffix) - 1);
    1189     z_len = strlen(z_suffix);
    1190 
    1191     /* Allocate all global buffers (for DYN_ALLOC option) */
    1192     ALLOC(uch, inbuf, INBUFSIZ + INBUF_EXTRA);
    1193     ALLOC(uch, outbuf, OUTBUFSIZ + OUTBUF_EXTRA);
    1194     ALLOC(ush, d_buf, DIST_BUFSIZE);
    1195     ALLOC(uch, window, 2L * WSIZE);
    1196     ALLOC(ush, tab_prefix, 1L << BITS);
    1197 
    1198     /* Initialise the CRC32 table */
    1199     crc_32_tab = bb_crc32_filltable(0);
    1200    
    1201     clear_bufs();
    1202     part_nb = 0;
    1203 
    1204     if (optind == argc) {
    1205         time_stamp = 0;
    1206         ifile_size = -1L;
    1207         zip(STDIN_FILENO, STDOUT_FILENO);
    1208     } else {
    1209         int i;
    1210 
    1211         for (i = optind; i < argc; i++) {
    1212             char *path = NULL;
    1213 
    1214             clear_bufs();
    1215             if (strcmp(argv[i], "-") == 0) {
    1216                 time_stamp = 0;
    1217                 ifile_size = -1L;
    1218                 inFileNum = STDIN_FILENO;
    1219                 outFileNum = STDOUT_FILENO;
    1220             } else {
    1221                 inFileNum = bb_xopen3(argv[i], O_RDONLY, 0);
    1222                 if (fstat(inFileNum, &statBuf) < 0)
    1223                     bb_perror_msg_and_die("%s", argv[i]);
    1224                 time_stamp = statBuf.st_ctime;
    1225                 ifile_size = statBuf.st_size;
    1226 
    1227                 if (!tostdout) {
    1228                     path = xmalloc(strlen(argv[i]) + 4);
    1229                     strcpy(path, argv[i]);
    1230                     strcat(path, ".gz");
    1231 
    1232                     /* Open output file */
    1233 #if (__GLIBC__ >= 2) && (__GLIBC_MINOR__ >= 1) && defined O_NOFOLLOW
    1234                     outFileNum =
    1235                         open(path, O_RDWR | O_CREAT | O_EXCL | O_NOFOLLOW);
    1236 #else
    1237                     outFileNum = open(path, O_RDWR | O_CREAT | O_EXCL);
    1238 #endif
    1239                     if (outFileNum < 0) {
    1240                         bb_perror_msg("%s", path);
    1241                         free(path);
    1242                         continue;
    1243                     }
    1244 
    1245                     /* Set permissions on the file */
    1246                     fchmod(outFileNum, statBuf.st_mode);
    1247                 } else
    1248                     outFileNum = STDOUT_FILENO;
    1249             }
    1250 
    1251             if (path == NULL && isatty(outFileNum) && force == 0) {
    1252                 bb_error_msg
    1253                     ("compressed data not written to a terminal. Use -f to force compression.");
    1254                 free(path);
    1255                 continue;
    1256             }
    1257 
    1258             result = zip(inFileNum, outFileNum);
    1259 
    1260             if (path != NULL) {
    1261                 close(inFileNum);
    1262                 close(outFileNum);
    1263 
    1264                 /* Delete the original file */
    1265                 if (result == OK)
    1266                     delFileName = argv[i];
    1267                 else
    1268                     delFileName = path;
    1269 
    1270                 if (unlink(delFileName) < 0)
    1271                     bb_perror_msg("%s", delFileName);
    1272             }
    1273 
    1274             free(path);
    1275         }
    1276     }
    1277 
    1278     return (exit_code);
    1279 }
     694#  define check_match(start, match, length) ((void)0)
     695#endif
     696
    1280697
    1281698/* trees.c -- output deflated data using Huffman coding
    … …  
    1285702 */
    1286703
    1287 /*
    1288  *  PURPOSE
    1289  *
     704/*  PURPOSE
    1290705 *      Encode various sets of source values using variable-length
    1291706 *      binary code trees.
    1292707 *
    1293708 *  DISCUSSION
    1294  *
    1295709 *      The PKZIP "deflation" process uses several Huffman trees. The more
    1296710 *      common source values are represented by shorter bit sequences.
    … …  
    1304718 *
    1305719 *  REFERENCES
    1306  *
    1307720 *      Lynch, Thomas J.
    1308721 *          Data Compression:  Techniques and Applications, pp. 53-55.
    … …  
    1318731 *
    1319732 *  INTERFACE
     733 *      void ct_init()
     734 *          Allocate the match buffer, initialize the various tables [and save
     735 *          the location of the internal file attribute (ascii/binary) and
     736 *          method (DEFLATE/STORE) -- deleted in bbox]
    1320737 *
    1321  *      void ct_init (ush *attr, int *methodp)
    1322  *          Allocate the match buffer, initialize the various tables and save
    1323  *          the location of the internal file attribute (ascii/binary) and
    1324  *          method (DEFLATE/STORE)
    1325  *
    1326  *      void ct_tally (int dist, int lc);
     738 *      void ct_tally(int dist, int lc);
    1327739 *          Save the match info and tally the frequency counts.
    1328740 *
    1329  *      long flush_block (char *buf, ulg stored_len, int eof)
     741 *      ulg flush_block(char *buf, ulg stored_len, int eof)
    1330742 *          Determine the best encoding for the current block: dynamic trees,
    1331743 *          static trees or store, and output the encoded block to the zip
    1332744 *          file. Returns the total compressed length for the file so far.
    1333  *
    1334  */
    1335 
    1336 /* ===========================================================================
    1337  * Constants
    1338745 */
    1339746
    … …  
    1362769/* number of codes used to transfer the bit lengths */
    1363770
    1364 typedef uch extra_bits_t;
    1365 
    1366771/* extra bits for each length code */
    1367 static const extra_bits_t extra_lbits[LENGTH_CODES]
    1368     = { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4,
     772static const uint8_t extra_lbits[LENGTH_CODES] ALIGN1 = {
     773    0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4,
    1369774    4, 4, 5, 5, 5, 5, 0
    1370775};
    1371776
    1372777/* extra bits for each distance code */
    1373 static const extra_bits_t extra_dbits[D_CODES]
    1374     = { 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9,
     778static const uint8_t extra_dbits[D_CODES] ALIGN1 = {
     779    0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9,
    1375780    10, 10, 11, 11, 12, 12, 13, 13
    1376781};
    1377782
    1378783/* extra bits for each bit length code */
    1379 static const extra_bits_t extra_blbits[BL_CODES]
    1380 = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7 };
     784static const uint8_t extra_blbits[BL_CODES] ALIGN1 = {
     785    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7 };
     786
     787/* number of codes at each bit length for an optimal tree */
     788static const uint8_t bl_order[BL_CODES] ALIGN1 = {
     789    16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
    1381790
    1382791#define STORED_BLOCK 0
    … …  
    1419828 * if we rely on DIST_BUFSIZE == LIT_BUFSIZE.
    1420829 */
    1421 #if LIT_BUFSIZE > INBUFSIZ
    1422 #error cannot overlay l_buf and inbuf
    1423 #endif
    1424830#define REP_3_6      16
    1425831/* repeat previous bit length 3-6 times (2 bits of repeat count) */
    … …  
    1430836
    1431837/* ===========================================================================
    1432  * Local data
    1433  */
    1434 
     838*/
    1435839/* Data structure describing a single value and its code string. */
    1436840typedef struct ct_data {
    … …  
    1450854#define Len  dl.len
    1451855
    1452 #define HEAP_SIZE (2*L_CODES+1)
     856#define HEAP_SIZE (2*L_CODES + 1)
    1453857/* maximum heap size */
    1454 
    1455 static ct_data dyn_ltree[HEAP_SIZE];    /* literal and length tree */
    1456 static ct_data dyn_dtree[2 * D_CODES + 1];  /* distance tree */
    1457 
    1458 static ct_data static_ltree[L_CODES + 2];
    1459 
    1460 /* The static literal tree. Since the bit lengths are imposed, there is no
    1461  * need for the L_CODES extra codes used during heap construction. However
    1462  * The codes 286 and 287 are needed to build a canonical tree (see ct_init
    1463  * below).
    1464  */
    1465 
    1466 static ct_data static_dtree[D_CODES];
    1467 
    1468 /* The static distance tree. (Actually a trivial tree since all codes use
    1469  * 5 bits.)
    1470  */
    1471 
    1472 static ct_data bl_tree[2 * BL_CODES + 1];
    1473 
    1474 /* Huffman tree for the bit lengths */
    1475858
    1476859typedef struct tree_desc {
    1477860    ct_data *dyn_tree;  /* the dynamic tree */
    1478861    ct_data *static_tree;   /* corresponding static tree or NULL */
    1479     const extra_bits_t *extra_bits; /* extra bits for each code or NULL */
     862    const uint8_t *extra_bits;  /* extra bits for each code or NULL */
    1480863    int extra_base;     /* base index for extra_bits */
    1481864    int elems;          /* max number of elements in the tree */
    … …  
    1484867} tree_desc;
    1485868
    1486 static tree_desc l_desc =
    1487     { dyn_ltree, static_ltree, extra_lbits, LITERALS + 1, L_CODES,
    1488     MAX_BITS, 0
    1489 };
    1490 
    1491 static tree_desc d_desc =
    1492     { dyn_dtree, static_dtree, extra_dbits, 0, D_CODES, MAX_BITS, 0 };
    1493 
    1494 static tree_desc bl_desc =
    1495     { bl_tree, (ct_data *) 0, extra_blbits, 0, BL_CODES, MAX_BL_BITS,
    1496     0
    1497 };
    1498 
    1499 
    1500 static ush bl_count[MAX_BITS + 1];
    1501 
    1502 /* number of codes at each bit length for an optimal tree */
    1503 
    1504 static const uch bl_order[BL_CODES]
    1505 = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
     869struct globals2 {
     870
     871    ush heap[HEAP_SIZE];     /* heap used to build the Huffman trees */
     872    int heap_len;            /* number of elements in the heap */
     873    int heap_max;            /* element of largest frequency */
     874
     875/* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
     876 * The same heap array is used to build all trees.
     877 */
     878
     879    ct_data dyn_ltree[HEAP_SIZE];   /* literal and length tree */
     880    ct_data dyn_dtree[2 * D_CODES + 1]; /* distance tree */
     881
     882    ct_data static_ltree[L_CODES + 2];
     883
     884/* The static literal tree. Since the bit lengths are imposed, there is no
     885 * need for the L_CODES extra codes used during heap construction. However
     886 * The codes 286 and 287 are needed to build a canonical tree (see ct_init
     887 * below).
     888 */
     889
     890    ct_data static_dtree[D_CODES];
     891
     892/* The static distance tree. (Actually a trivial tree since all codes use
     893 * 5 bits.)
     894 */
     895
     896    ct_data bl_tree[2 * BL_CODES + 1];
     897
     898/* Huffman tree for the bit lengths */
     899
     900    tree_desc l_desc;
     901    tree_desc d_desc;
     902    tree_desc bl_desc;
     903
     904    ush bl_count[MAX_BITS + 1];
    1506905
    1507906/* The lengths of the bit length codes are sent in order of decreasing
    … …  
    1509908 */
    1510909
    1511 static int heap[2 * L_CODES + 1];   /* heap used to build the Huffman trees */
    1512 static int heap_len;    /* number of elements in the heap */
    1513 static int heap_max;    /* element of largest frequency */
    1514 
    1515 /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
    1516  * The same heap array is used to build all trees.
    1517  */
    1518 
    1519 static uch depth[2 * L_CODES + 1];
     910    uch depth[2 * L_CODES + 1];
    1520911
    1521912/* Depth of each subtree used as tie breaker for trees of equal frequency */
    1522913
    1523 static uch length_code[MAX_MATCH - MIN_MATCH + 1];
     914    uch length_code[MAX_MATCH - MIN_MATCH + 1];
    1524915
    1525916/* length code for each normalized match length (0 == MIN_MATCH) */
    1526917
    1527 static uch dist_code[512];
     918    uch dist_code[512];
    1528919
    1529920/* distance codes. The first 256 values correspond to the distances
    … …  
    1532923 */
    1533924
    1534 static int base_length[LENGTH_CODES];
     925    int base_length[LENGTH_CODES];
    1535926
    1536927/* First normalized length for each code (0 = MIN_MATCH) */
    1537928
    1538 static int base_dist[D_CODES];
     929    int base_dist[D_CODES];
    1539930
    1540931/* First normalized distance for each code (0 = distance of 1) */
    1541932
    1542 #define l_buf inbuf
    1543 /* DECLARE(uch, l_buf, LIT_BUFSIZE);  buffer for literals or lengths */
    1544 
    1545 /* DECLARE(ush, d_buf, DIST_BUFSIZE); buffer for distances */
    1546 
    1547 static uch flag_buf[(LIT_BUFSIZE / 8)];
     933    uch flag_buf[LIT_BUFSIZE / 8];
    1548934
    1549935/* flag_buf is a bit array distinguishing literals from lengths in
    … …  
    1551937 */
    1552938
    1553 static unsigned last_lit;   /* running index in l_buf */
    1554 static unsigned last_dist;  /* running index in d_buf */
    1555 static unsigned last_flags; /* running index in flag_buf */
    1556 static uch flags;       /* current flags not yet saved in flag_buf */
    1557 static uch flag_bit;    /* current bit used in flags */
     939    unsigned last_lit;       /* running index in l_buf */
     940    unsigned last_dist;      /* running index in d_buf */
     941    unsigned last_flags;     /* running index in flag_buf */
     942    uch flags;               /* current flags not yet saved in flag_buf */
     943    uch flag_bit;            /* current bit used in flags */
    1558944
    1559945/* bits are filled in flags starting at bit 0 (least significant).
    … …  
    1562948 */
    1563949
    1564 static ulg opt_len;     /* bit length of current block with optimal trees */
    1565 static ulg static_len;  /* bit length of current block with static trees */
    1566 
    1567 static ulg compressed_len;  /* total bit length of compressed file */
    1568 
    1569 
    1570 static ush *file_type;  /* pointer to UNKNOWN, BINARY or ASCII */
    1571 static int *file_method;    /* pointer to DEFLATE or STORE */
    1572 
    1573 /* ===========================================================================
    1574  * Local (static) routines in this file.
    1575  */
    1576 
    1577 static void init_block(void);
    1578 static void pqdownheap(ct_data * tree, int k);
    1579 static void gen_bitlen(tree_desc * desc);
     950    ulg opt_len;             /* bit length of current block with optimal trees */
     951    ulg static_len;          /* bit length of current block with static trees */
     952
     953    ulg compressed_len;      /* total bit length of compressed file */
     954};
     955
     956#define G2ptr ((struct globals2*)(ptr_to_globals))
     957#define G2 (*G2ptr)
     958
     959
     960/* ===========================================================================
     961 */
    1580962static void gen_codes(ct_data * tree, int max_code);
    1581963static void build_tree(tree_desc * desc);
    … …  
    1585967static void send_all_trees(int lcodes, int dcodes, int blcodes);
    1586968static void compress_block(ct_data * ltree, ct_data * dtree);
    1587 static void set_file_type(void);
    1588969
    1589970
    1590971#ifndef DEBUG
    1591 #  define send_code(c, tree) send_bits(tree[c].Code, tree[c].Len)
    1592    /* Send a code of the given tree. c and tree must not have side effects */
    1593 
    1594 #else                           /* DEBUG */
    1595 #  define send_code(c, tree) \
    1596      { if (verbose>1) bb_error_msg("\ncd %3d ",(c)); \
    1597        send_bits(tree[c].Code, tree[c].Len); }
    1598 #endif
    1599 
    1600 #define d_code(dist) \
    1601    ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)])
     972/* Send a code of the given tree. c and tree must not have side effects */
     973#  define SEND_CODE(c, tree) send_bits(tree[c].Code, tree[c].Len)
     974#else
     975#  define SEND_CODE(c, tree) \
     976{ \
     977    if (verbose > 1) bb_error_msg("\ncd %3d ",(c)); \
     978    send_bits(tree[c].Code, tree[c].Len); \
     979}
     980#endif
     981
     982#define D_CODE(dist) \
     983    ((dist) < 256 ? G2.dist_code[dist] : G2.dist_code[256 + ((dist)>>7)])
    1602984/* Mapping from a distance to a distance code. dist is the distance - 1 and
    1603985 * must not have side effects. dist_code[256] and dist_code[257] are never
    1604986 * used.
    1605  */
    1606 
    1607 /* the arguments must not have side effects */
    1608 
    1609 /* ===========================================================================
    1610  * Allocate the match buffer, initialize the various tables and save the
    1611  * location of the internal file attribute (ascii/binary) and method
    1612  * (DEFLATE/STORE).
    1613  */
    1614 static void ct_init(ush * attr, int *methodp)
    1615 {
    1616     int n;              /* iterates over tree elements */
    1617     int bits;           /* bit counter */
    1618     int length;         /* length value */
    1619     int code;           /* code value */
    1620     int dist;           /* distance index */
    1621 
    1622     file_type = attr;
    1623     file_method = methodp;
    1624     compressed_len = 0L;
    1625 
    1626     if (static_dtree[0].Len != 0)
    1627         return;         /* ct_init already called */
    1628 
    1629     /* Initialize the mapping length (0..255) -> length code (0..28) */
    1630     length = 0;
    1631     for (code = 0; code < LENGTH_CODES - 1; code++) {
    1632         base_length[code] = length;
    1633         for (n = 0; n < (1 << extra_lbits[code]); n++) {
    1634             length_code[length++] = (uch) code;
    1635         }
    1636     }
    1637     Assert(length == 256, "ct_init: length != 256");
    1638     /* Note that the length 255 (match length 258) can be represented
    1639      * in two different ways: code 284 + 5 bits or code 285, so we
    1640      * overwrite length_code[255] to use the best encoding:
    1641      */
    1642     length_code[length - 1] = (uch) code;
    1643 
    1644     /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
    1645     dist = 0;
    1646     for (code = 0; code < 16; code++) {
    1647         base_dist[code] = dist;
    1648         for (n = 0; n < (1 << extra_dbits[code]); n++) {
    1649             dist_code[dist++] = (uch) code;
    1650         }
    1651     }
    1652     Assert(dist == 256, "ct_init: dist != 256");
    1653     dist >>= 7;         /* from now on, all distances are divided by 128 */
    1654     for (; code < D_CODES; code++) {
    1655         base_dist[code] = dist << 7;
    1656         for (n = 0; n < (1 << (extra_dbits[code] - 7)); n++) {
    1657             dist_code[256 + dist++] = (uch) code;
    1658         }
    1659     }
    1660     Assert(dist == 256, "ct_init: 256+dist != 512");
    1661 
    1662     /* Construct the codes of the static literal tree */
    1663     for (bits = 0; bits <= MAX_BITS; bits++)
    1664         bl_count[bits] = 0;
    1665     n = 0;
    1666     while (n <= 143)
    1667         static_ltree[n++].Len = 8, bl_count[8]++;
    1668     while (n <= 255)
    1669         static_ltree[n++].Len = 9, bl_count[9]++;
    1670     while (n <= 279)
    1671         static_ltree[n++].Len = 7, bl_count[7]++;
    1672     while (n <= 287)
    1673         static_ltree[n++].Len = 8, bl_count[8]++;
    1674     /* Codes 286 and 287 do not exist, but we must include them in the
    1675      * tree construction to get a canonical Huffman tree (longest code
    1676      * all ones)
    1677      */
    1678     gen_codes((ct_data *) static_ltree, L_CODES + 1);
    1679 
    1680     /* The static distance tree is trivial: */
    1681     for (n = 0; n < D_CODES; n++) {
    1682         static_dtree[n].Len = 5;
    1683         static_dtree[n].Code = bi_reverse(n, 5);
    1684     }
    1685 
    1686     /* Initialize the first block of the first file: */
    1687     init_block();
    1688 }
     987 * The arguments must not have side effects.
     988 */
     989
    1689990
    1690991/* ===========================================================================
    … …  
    1693994static void init_block(void)
    1694995{
    1695     int n;              /* iterates over tree elements */
     996    int n; /* iterates over tree elements */
    1696997
    1697998    /* Initialize the trees. */
    1698999    for (n = 0; n < L_CODES; n++)
    1699         dyn_ltree[n].Freq = 0;
     1000        G2.dyn_ltree[n].Freq = 0;
    17001001    for (n = 0; n < D_CODES; n++)
    1701         dyn_dtree[n].Freq = 0;
     1002        G2.dyn_dtree[n].Freq = 0;
    17021003    for (n = 0; n < BL_CODES; n++)
    1703         bl_tree[n].Freq = 0;
    1704 
    1705     dyn_ltree[END_BLOCK].Freq = 1;
    1706     opt_len = static_len = 0L;
    1707     last_lit = last_dist = last_flags = 0;
    1708     flags = 0;
    1709     flag_bit = 1;
    1710 }
    1711 
    1712 #define SMALLEST 1
    1713 /* Index within the heap array of least frequent node in the Huffman tree */
    1714 
    1715 
    1716 /* ===========================================================================
    1717  * Remove the smallest element from the heap and recreate the heap with
    1718  * one less element. Updates heap and heap_len.
    1719  */
    1720 #define pqremove(tree, top) \
    1721 {\
    1722     top = heap[SMALLEST]; \
    1723     heap[SMALLEST] = heap[heap_len--]; \
    1724     pqdownheap(tree, SMALLEST); \
    1725 }
    1726 
    1727 /* ===========================================================================
    1728  * Compares to subtrees, using the tree depth as tie breaker when
    1729  * the subtrees have equal frequency. This minimizes the worst case length.
    1730  */
    1731 #define smaller(tree, n, m) \
    1732    (tree[n].Freq < tree[m].Freq || \
    1733    (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
     1004        G2.bl_tree[n].Freq = 0;
     1005
     1006    G2.dyn_ltree[END_BLOCK].Freq = 1;
     1007    G2.opt_len = G2.static_len = 0;
     1008    G2.last_lit = G2.last_dist = G2.last_flags = 0;
     1009    G2.flags = 0;
     1010    G2.flag_bit = 1;
     1011}
     1012
    17341013
    17351014/* ===========================================================================
    … …  
    17391018 * two sons).
    17401019 */
     1020
     1021/* Compares to subtrees, using the tree depth as tie breaker when
     1022 * the subtrees have equal frequency. This minimizes the worst case length. */
     1023#define SMALLER(tree, n, m) \
     1024    (tree[n].Freq < tree[m].Freq \
     1025    || (tree[n].Freq == tree[m].Freq && G2.depth[n] <= G2.depth[m]))
     1026
    17411027static void pqdownheap(ct_data * tree, int k)
    17421028{
    1743     int v = heap[k];
     1029    int v = G2.heap[k];
    17441030    int j = k << 1;     /* left son of k */
    17451031
    1746     while (j <= heap_len) {
     1032    while (j <= G2.heap_len) {
    17471033        /* Set j to the smallest of the two sons: */
    1748         if (j < heap_len && smaller(tree, heap[j + 1], heap[j]))
     1034        if (j < G2.heap_len && SMALLER(tree, G2.heap[j + 1], G2.heap[j]))
    17491035            j++;
    17501036
    17511037        /* Exit if v is smaller than both sons */
    1752         if (smaller(tree, v, heap[j]))
     1038        if (SMALLER(tree, v, G2.heap[j]))
    17531039            break;
    17541040
    17551041        /* Exchange v with the smallest son */
    1756         heap[k] = heap[j];
     1042        G2.heap[k] = G2.heap[j];
    17571043        k = j;
    17581044
    … …  
    17601046        j <<= 1;
    17611047    }
    1762     heap[k] = v;
    1763 }
     1048    G2.heap[k] = v;
     1049}
     1050
    17641051
    17651052/* ===========================================================================
    … …  
    17761063{
    17771064    ct_data *tree = desc->dyn_tree;
    1778     const extra_bits_t *extra = desc->extra_bits;
     1065    const uint8_t *extra = desc->extra_bits;
    17791066    int base = desc->extra_base;
    17801067    int max_code = desc->max_code;
    … …  
    17891076
    17901077    for (bits = 0; bits <= MAX_BITS; bits++)
    1791         bl_count[bits] = 0;
     1078        G2.bl_count[bits] = 0;
    17921079
    17931080    /* In a first pass, compute the optimal bit lengths (which may
    17941081     * overflow in the case of the bit length tree).
    17951082     */
    1796     tree[heap[heap_max]].Len = 0;   /* root of the heap */
    1797 
    1798     for (h = heap_max + 1; h < HEAP_SIZE; h++) {
    1799         n = heap[h];
     1083    tree[G2.heap[G2.heap_max]].Len = 0; /* root of the heap */
     1084
     1085    for (h = G2.heap_max + 1; h < HEAP_SIZE; h++) {
     1086        n = G2.heap[h];
    18001087        bits = tree[tree[n].Dad].Len + 1;
    1801         if (bits > max_length)
    1802             bits = max_length, overflow++;
     1088        if (bits > max_length) {
     1089            bits = max_length;
     1090            overflow++;
     1091        }
    18031092        tree[n].Len = (ush) bits;
    18041093        /* We overwrite tree[n].Dad which is no longer needed */
    … …  
    18071096            continue;   /* not a leaf node */
    18081097
    1809         bl_count[bits]++;
     1098        G2.bl_count[bits]++;
    18101099        xbits = 0;
    18111100        if (n >= base)
    18121101            xbits = extra[n - base];
    18131102        f = tree[n].Freq;
    1814         opt_len += (ulg) f *(bits + xbits);
     1103        G2.opt_len += (ulg) f *(bits + xbits);
    18151104
    18161105        if (stree)
    1817             static_len += (ulg) f *(stree[n].Len + xbits);
     1106            G2.static_len += (ulg) f * (stree[n].Len + xbits);
    18181107    }
    18191108    if (overflow == 0)
    … …  
    18261115    do {
    18271116        bits = max_length - 1;
    1828         while (bl_count[bits] == 0)
     1117        while (G2.bl_count[bits] == 0)
    18291118            bits--;
    1830         bl_count[bits]--;   /* move one leaf down the tree */
    1831         bl_count[bits + 1] += 2;    /* move one overflow item as its brother */
    1832         bl_count[max_length]--;
     1119        G2.bl_count[bits]--;    /* move one leaf down the tree */
     1120        G2.bl_count[bits + 1] += 2; /* move one overflow item as its brother */
     1121        G2.bl_count[max_length]--;
    18331122        /* The brother of the overflow item also moves one step up,
    18341123         * but this does not affect bl_count[max_length]
    … …  
    18431132     */
    18441133    for (bits = max_length; bits != 0; bits--) {
    1845         n = bl_count[bits];
     1134        n = G2.bl_count[bits];
    18461135        while (n != 0) {
    1847             m = heap[--h];
     1136            m = G2.heap[--h];
    18481137            if (m > max_code)
    18491138                continue;
    18501139            if (tree[m].Len != (unsigned) bits) {
    1851                 Trace((stderr, "code %d bits %d->%d\n", m, tree[m].Len,
    1852                        bits));
    1853                 opt_len +=
    1854                     ((long) bits - (long) tree[m].Len) * (long) tree[m].Freq;
    1855                 tree[m].Len = (ush) bits;
     1140                Trace((stderr, "code %d bits %d->%d\n", m, tree[m].Len, bits));
     1141                G2.opt_len += ((int32_t) bits - tree[m].Len) * tree[m].Freq;
     1142                tree[m].Len = bits;
    18561143            }
    18571144            n--;
    … …  
    18591146    }
    18601147}
     1148
    18611149
    18621150/* ===========================================================================
    … …  
    18791167     */
    18801168    for (bits = 1; bits <= MAX_BITS; bits++) {
    1881         next_code[bits] = code = (code + bl_count[bits - 1]) << 1;
     1169        next_code[bits] = code = (code + G2.bl_count[bits - 1]) << 1;
    18821170    }
    18831171    /* Check that the bit counts in bl_count are consistent. The last code
    18841172     * must be all ones.
    18851173     */
    1886     Assert(code + bl_count[MAX_BITS] - 1 == (1 << MAX_BITS) - 1,
     1174    Assert(code + G2.bl_count[MAX_BITS] - 1 == (1 << MAX_BITS) - 1,
    18871175           "inconsistent bit counts");
    18881176    Tracev((stderr, "\ngen_codes: max_code %d ", max_code));
    … …  
    18961184        tree[n].Code = bi_reverse(next_code[len]++, len);
    18971185
    1898         Tracec(tree != static_ltree,
     1186        Tracec(tree != G2.static_ltree,
    18991187               (stderr, "\nn %3d %c l %2d c %4x (%x) ", n,
    19001188                (isgraph(n) ? n : ' '), len, tree[n].Code,
    … …  
    19021190    }
    19031191}
     1192
    19041193
    19051194/* ===========================================================================
    … …  
    19111200 *     also updated if stree is not null. The field max_code is set.
    19121201 */
     1202
     1203/* Remove the smallest element from the heap and recreate the heap with
     1204 * one less element. Updates heap and heap_len. */
     1205
     1206#define SMALLEST 1
     1207/* Index within the heap array of least frequent node in the Huffman tree */
     1208
     1209#define PQREMOVE(tree, top) \
     1210do { \
     1211    top = G2.heap[SMALLEST]; \
     1212    G2.heap[SMALLEST] = G2.heap[G2.heap_len--]; \
     1213    pqdownheap(tree, SMALLEST); \
     1214} while (0)
     1215
    19131216static void build_tree(tree_desc * desc)
    19141217{
    … …  
    19241227     * heap[0] is not used.
    19251228     */
    1926     heap_len = 0, heap_max = HEAP_SIZE;
     1229    G2.heap_len = 0;
     1230    G2.heap_max = HEAP_SIZE;
    19271231
    19281232    for (n = 0; n < elems; n++) {
    19291233        if (tree[n].Freq != 0) {
    1930             heap[++heap_len] = max_code = n;
    1931             depth[n] = 0;
     1234            G2.heap[++G2.heap_len] = max_code = n;
     1235            G2.depth[n] = 0;
    19321236        } else {
    19331237            tree[n].Len = 0;
    … …  
    19401244     * two codes of non zero frequency.
    19411245     */
    1942     while (heap_len < 2) {
    1943         int new = heap[++heap_len] = (max_code < 2 ? ++max_code : 0);
     1246    while (G2.heap_len < 2) {
     1247        int new = G2.heap[++G2.heap_len] = (max_code < 2 ? ++max_code : 0);
    19441248
    19451249        tree[new].Freq = 1;
    1946         depth[new] = 0;
    1947         opt_len--;
     1250        G2.depth[new] = 0;
     1251        G2.opt_len--;
    19481252        if (stree)
    1949             static_len -= stree[new].Len;
     1253            G2.static_len -= stree[new].Len;
    19501254        /* new is 0 or 1 so it does not have extra bits */
    19511255    }
    … …  
    19551259     * establish sub-heaps of increasing lengths:
    19561260     */
    1957     for (n = heap_len / 2; n >= 1; n--)
     1261    for (n = G2.heap_len / 2; n >= 1; n--)
    19581262        pqdownheap(tree, n);
    19591263
    … …  
    19621266     */
    19631267    do {
    1964         pqremove(tree, n);  /* n = node of least frequency */
    1965         m = heap[SMALLEST]; /* m = node of next least frequency */
    1966 
    1967         heap[--heap_max] = n;   /* keep the nodes sorted by frequency */
    1968         heap[--heap_max] = m;
     1268        PQREMOVE(tree, n);  /* n = node of least frequency */
     1269        m = G2.heap[SMALLEST];  /* m = node of next least frequency */
     1270
     1271        G2.heap[--G2.heap_max] = n; /* keep the nodes sorted by frequency */
     1272        G2.heap[--G2.heap_max] = m;
    19691273
    19701274        /* Create a new node father of n and m */
    19711275        tree[node].Freq = tree[n].Freq + tree[m].Freq;
    1972         depth[node] = (uch) (MAX(depth[n], depth[m]) + 1);
     1276        G2.depth[node] = MAX(G2.depth[n], G2.depth[m]) + 1;
    19731277        tree[n].Dad = tree[m].Dad = (ush) node;
    19741278#ifdef DUMP_BL_TREE
    1975         if (tree == bl_tree) {
     1279        if (tree == G2.bl_tree) {
    19761280            bb_error_msg("\nnode %d(%d), sons %d(%d) %d(%d)",
    19771281                    node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
    … …  
    19791283#endif
    19801284        /* and insert the new node in the heap */
    1981         heap[SMALLEST] = node++;
     1285        G2.heap[SMALLEST] = node++;
    19821286        pqdownheap(tree, SMALLEST);
    19831287
    1984     } while (heap_len >= 2);
    1985 
    1986     heap[--heap_max] = heap[SMALLEST];
     1288    } while (G2.heap_len >= 2);
     1289
     1290    G2.heap[--G2.heap_max] = G2.heap[SMALLEST];
    19871291
    19881292    /* At this point, the fields freq and dad are set. We can now
    … …  
    19941298    gen_codes((ct_data *) tree, max_code);
    19951299}
     1300
    19961301
    19971302/* ===========================================================================
    … …  
    20111316    int min_count = 4;  /* min repeat count */
    20121317
    2013     if (nextlen == 0)
    2014         max_count = 138, min_count = 3;
    2015     tree[max_code + 1].Len = (ush) 0xffff;  /* guard */
     1318    if (nextlen == 0) {
     1319        max_count = 138;
     1320        min_count = 3;
     1321    }
     1322    tree[max_code + 1].Len = 0xffff; /* guard */
    20161323
    20171324    for (n = 0; n <= max_code; n++) {
    20181325        curlen = nextlen;
    20191326        nextlen = tree[n + 1].Len;
    2020         if (++count < max_count && curlen == nextlen) {
     1327        if (++count < max_count && curlen == nextlen)
    20211328            continue;
    2022         } else if (count < min_count) {
    2023             bl_tree[curlen].Freq += count;
     1329
     1330        if (count < min_count) {
     1331            G2.bl_tree[curlen].Freq += count;
    20241332        } else if (curlen != 0) {
    20251333            if (curlen != prevlen)
    2026                 bl_tree[curlen].Freq++;
    2027             bl_tree[REP_3_6].Freq++;
     1334                G2.bl_tree[curlen].Freq++;
     1335            G2.bl_tree[REP_3_6].Freq++;
    20281336        } else if (count <= 10) {
    2029             bl_tree[REPZ_3_10].Freq++;
     1337            G2.bl_tree[REPZ_3_10].Freq++;
    20301338        } else {
    2031             bl_tree[REPZ_11_138].Freq++;
     1339            G2.bl_tree[REPZ_11_138].Freq++;
    20321340        }
    20331341        count = 0;
    20341342        prevlen = curlen;
     1343
     1344        max_count = 7;
     1345        min_count = 4;
    20351346        if (nextlen == 0) {
    2036             max_count = 138, min_count = 3;
     1347            max_count = 138;
     1348            min_count = 3;
    20371349        } else if (curlen == nextlen) {
    2038             max_count = 6, min_count = 3;
    2039         } else {
    2040             max_count = 7, min_count = 4;
     1350            max_count = 6;
     1351            min_count = 3;
    20411352        }
    20421353    }
    20431354}
     1355
    20441356
    20451357/* ===========================================================================
    … …  
    20681380        } else if (count < min_count) {
    20691381            do {
    2070                 send_code(curlen, bl_tree);
    2071             } while (--count != 0);
    2072 
     1382                SEND_CODE(curlen, G2.bl_tree);
     1383            } while (--count);
    20731384        } else if (curlen != 0) {
    20741385            if (curlen != prevlen) {
    2075                 send_code(curlen, bl_tree);
     1386                SEND_CODE(curlen, G2.bl_tree);
    20761387                count--;
    20771388            }
    20781389            Assert(count >= 3 && count <= 6, " 3_6?");
    2079             send_code(REP_3_6, bl_tree);
     1390            SEND_CODE(REP_3_6, G2.bl_tree);
    20801391            send_bits(count - 3, 2);
    2081 
    20821392        } else if (count <= 10) {
    2083             send_code(REPZ_3_10, bl_tree);
     1393            SEND_CODE(REPZ_3_10, G2.bl_tree);
    20841394            send_bits(count - 3, 3);
    2085 
    20861395        } else {
    2087             send_code(REPZ_11_138, bl_tree);
     1396            SEND_CODE(REPZ_11_138, G2.bl_tree);
    20881397            send_bits(count - 11, 7);
    20891398        }
    … …  
    20911400        prevlen = curlen;
    20921401        if (nextlen == 0) {
    2093             max_count = 138, min_count = 3;
     1402            max_count = 138;
     1403            min_count = 3;
    20941404        } else if (curlen == nextlen) {
    2095             max_count = 6, min_count = 3;
     1405            max_count = 6;
     1406            min_count = 3;
    20961407        } else {
    2097             max_count = 7, min_count = 4;
     1408            max_count = 7;
     1409            min_count = 4;
    20981410        }
    20991411    }
    21001412}
     1413
    21011414
    21021415/* ===========================================================================
    … …  
    21091422
    21101423    /* Determine the bit length frequencies for literal and distance trees */
    2111     scan_tree((ct_data *) dyn_ltree, l_desc.max_code);
    2112     scan_tree((ct_data *) dyn_dtree, d_desc.max_code);
     1424    scan_tree(G2.dyn_ltree, G2.l_desc.max_code);
     1425    scan_tree(G2.dyn_dtree, G2.d_desc.max_code);
    21131426
    21141427    /* Build the bit length tree: */
    2115     build_tree((tree_desc *) (&bl_desc));
     1428    build_tree(&G2.bl_desc);
    21161429    /* opt_len now includes the length of the tree representations, except
    21171430     * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
    … …  
    21231436     */
    21241437    for (max_blindex = BL_CODES - 1; max_blindex >= 3; max_blindex--) {
    2125         if (bl_tree[bl_order[max_blindex]].Len != 0)
     1438        if (G2.bl_tree[bl_order[max_blindex]].Len != 0)
    21261439            break;
    21271440    }
    21281441    /* Update opt_len to include the bit length tree and counts */
    2129     opt_len += 3 * (max_blindex + 1) + 5 + 5 + 4;
    2130     Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", opt_len, static_len));
     1442    G2.opt_len += 3 * (max_blindex + 1) + 5 + 5 + 4;
     1443    Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", G2.opt_len, G2.static_len));
    21311444
    21321445    return max_blindex;
    21331446}
     1447
    21341448
    21351449/* ===========================================================================
    … …  
    21511465    for (rank = 0; rank < blcodes; rank++) {
    21521466        Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
    2153         send_bits(bl_tree[bl_order[rank]].Len, 3);
    2154     }
    2155     Tracev((stderr, "\nbl tree: sent %ld", bits_sent));
    2156 
    2157     send_tree((ct_data *) dyn_ltree, lcodes - 1);   /* send the literal tree */
    2158     Tracev((stderr, "\nlit tree: sent %ld", bits_sent));
    2159 
    2160     send_tree((ct_data *) dyn_dtree, dcodes - 1);   /* send the distance tree */
    2161     Tracev((stderr, "\ndist tree: sent %ld", bits_sent));
    2162 }
     1467        send_bits(G2.bl_tree[bl_order[rank]].Len, 3);
     1468    }
     1469    Tracev((stderr, "\nbl tree: sent %ld", G1.bits_sent));
     1470
     1471    send_tree((ct_data *) G2.dyn_ltree, lcodes - 1);    /* send the literal tree */
     1472    Tracev((stderr, "\nlit tree: sent %ld", G1.bits_sent));
     1473
     1474    send_tree((ct_data *) G2.dyn_dtree, dcodes - 1);    /* send the distance tree */
     1475    Tracev((stderr, "\ndist tree: sent %ld", G1.bits_sent));
     1476}
     1477
     1478
     1479/* ===========================================================================
     1480 * Save the match info and tally the frequency counts. Return true if
     1481 * the current block must be flushed.
     1482 */
     1483static int ct_tally(int dist, int lc)
     1484{
     1485    G1.l_buf[G2.last_lit++] = lc;
     1486    if (dist == 0) {
     1487        /* lc is the unmatched char */
     1488        G2.dyn_ltree[lc].Freq++;
     1489    } else {
     1490        /* Here, lc is the match length - MIN_MATCH */
     1491        dist--;         /* dist = match distance - 1 */
     1492        Assert((ush) dist < (ush) MAX_DIST
     1493         && (ush) lc <= (ush) (MAX_MATCH - MIN_MATCH)
     1494         && (ush) D_CODE(dist) < (ush) D_CODES, "ct_tally: bad match"
     1495        );
     1496
     1497        G2.dyn_ltree[G2.length_code[lc] + LITERALS + 1].Freq++;
     1498        G2.dyn_dtree[D_CODE(dist)].Freq++;
     1499
     1500        G1.d_buf[G2.last_dist++] = dist;
     1501        G2.flags |= G2.flag_bit;
     1502    }
     1503    G2.flag_bit <<= 1;
     1504
     1505    /* Output the flags if they fill a byte: */
     1506    if ((G2.last_lit & 7) == 0) {
     1507        G2.flag_buf[G2.last_flags++] = G2.flags;
     1508        G2.flags = 0;
     1509        G2.flag_bit = 1;
     1510    }
     1511    /* Try to guess if it is profitable to stop the current block here */
     1512    if ((G2.last_lit & 0xfff) == 0) {
     1513        /* Compute an upper bound for the compressed length */
     1514        ulg out_length = G2.last_lit * 8L;
     1515        ulg in_length = (ulg) G1.strstart - G1.block_start;
     1516        int dcode;
     1517
     1518        for (dcode = 0; dcode < D_CODES; dcode++) {
     1519            out_length += G2.dyn_dtree[dcode].Freq * (5L + extra_dbits[dcode]);
     1520        }
     1521        out_length >>= 3;
     1522        Trace((stderr,
     1523               "\nlast_lit %u, last_dist %u, in %ld, out ~%ld(%ld%%) ",
     1524               G2.last_lit, G2.last_dist, in_length, out_length,
     1525               100L - out_length * 100L / in_length));
     1526        if (G2.last_dist < G2.last_lit / 2 && out_length < in_length / 2)
     1527            return 1;
     1528    }
     1529    return (G2.last_lit == LIT_BUFSIZE - 1 || G2.last_dist == DIST_BUFSIZE);
     1530    /* We avoid equality with LIT_BUFSIZE because of wraparound at 64K
     1531     * on 16 bit machines and because stored blocks are restricted to
     1532     * 64K-1 bytes.
     1533     */
     1534}
     1535
     1536/* ===========================================================================
     1537 * Send the block data compressed using the given Huffman trees
     1538 */
     1539static void compress_block(ct_data * ltree, ct_data * dtree)
     1540{
     1541    unsigned dist;          /* distance of matched string */
     1542    int lc;                 /* match length or unmatched char (if dist == 0) */
     1543    unsigned lx = 0;        /* running index in l_buf */
     1544    unsigned dx = 0;        /* running index in d_buf */
     1545    unsigned fx = 0;        /* running index in flag_buf */
     1546    uch flag = 0;           /* current flags */
     1547    unsigned code;          /* the code to send */
     1548    int extra;              /* number of extra bits to send */
     1549
     1550    if (G2.last_lit != 0) do {
     1551        if ((lx & 7) == 0)
     1552            flag = G2.flag_buf[fx++];
     1553        lc = G1.l_buf[lx++];
     1554        if ((flag & 1) == 0) {
     1555            SEND_CODE(lc, ltree);   /* send a literal byte */
     1556            Tracecv(isgraph(lc), (stderr, " '%c' ", lc));
     1557        } else {
     1558            /* Here, lc is the match length - MIN_MATCH */
     1559            code = G2.length_code[lc];
     1560            SEND_CODE(code + LITERALS + 1, ltree);  /* send the length code */
     1561            extra = extra_lbits[code];
     1562            if (extra != 0) {
     1563                lc -= G2.base_length[code];
     1564                send_bits(lc, extra);   /* send the extra length bits */
     1565            }
     1566            dist = G1.d_buf[dx++];
     1567            /* Here, dist is the match distance - 1 */
     1568            code = D_CODE(dist);
     1569            Assert(code < D_CODES, "bad d_code");
     1570
     1571            SEND_CODE(code, dtree); /* send the distance code */
     1572            extra = extra_dbits[code];
     1573            if (extra != 0) {
     1574                dist -= G2.base_dist[code];
     1575                send_bits(dist, extra); /* send the extra distance bits */
     1576            }
     1577        }           /* literal or match pair ? */
     1578        flag >>= 1;
     1579    } while (lx < G2.last_lit);
     1580
     1581    SEND_CODE(END_BLOCK, ltree);
     1582}
     1583
    21631584
    21641585/* ===========================================================================
    … …  
    21691590static ulg flush_block(char *buf, ulg stored_len, int eof)
    21701591{
    2171     ulg opt_lenb, static_lenb;  /* opt_len and static_len in bytes */
    2172     int max_blindex;    /* index of last bit length code of non zero freq */
    2173 
    2174     flag_buf[last_flags] = flags;   /* Save the flags for the last 8 items */
    2175 
    2176     /* Check if the file is ascii or binary */
    2177     if (*file_type == (ush) UNKNOWN)
    2178         set_file_type();
     1592    ulg opt_lenb, static_lenb;      /* opt_len and static_len in bytes */
     1593    int max_blindex;                /* index of last bit length code of non zero freq */
     1594
     1595    G2.flag_buf[G2.last_flags] = G2.flags;   /* Save the flags for the last 8 items */
    21791596
    21801597    /* Construct the literal and distance trees */
    2181     build_tree((tree_desc *) (&l_desc));
    2182     Tracev((stderr, "\nlit data: dyn %ld, stat %ld", opt_len, static_len));
    2183 
    2184     build_tree((tree_desc *) (&d_desc));
    2185     Tracev((stderr, "\ndist data: dyn %ld, stat %ld", opt_len, static_len));
     1598    build_tree(&G2.l_desc);
     1599    Tracev((stderr, "\nlit data: dyn %ld, stat %ld", G2.opt_len, G2.static_len));
     1600
     1601    build_tree(&G2.d_desc);
     1602    Tracev((stderr, "\ndist data: dyn %ld, stat %ld", G2.opt_len, G2.static_len));
    21861603    /* At this point, opt_len and static_len are the total bit lengths of
    21871604     * the compressed block data, excluding the tree representations.
    … …  
    21941611
    21951612    /* Determine the best encoding. Compute first the block length in bytes */
    2196     opt_lenb = (opt_len + 3 + 7) >> 3;
    2197     static_lenb = (static_len + 3 + 7) >> 3;
     1613    opt_lenb = (G2.opt_len + 3 + 7) >> 3;
     1614    static_lenb = (G2.static_len + 3 + 7) >> 3;
    21981615
    21991616    Trace((stderr,
    22001617           "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u dist %u ",
    2201            opt_lenb, opt_len, static_lenb, static_len, stored_len,
    2202            last_lit, last_dist));
     1618           opt_lenb, G2.opt_len, static_lenb, G2.static_len, stored_len,
     1619           G2.last_lit, G2.last_dist));
    22031620
    22041621    if (static_lenb <= opt_lenb)
    … …  
    22091626     * the whole file is transformed into a stored file:
    22101627     */
    2211     if (stored_len <= opt_lenb && eof && compressed_len == 0L && seekable()) {
     1628    if (stored_len <= opt_lenb && eof && G2.compressed_len == 0L && seekable()) {
    22121629        /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */
    2213         if (buf == (char *) 0)
     1630        if (buf == NULL)
    22141631            bb_error_msg("block vanished");
    22151632
    22161633        copy_block(buf, (unsigned) stored_len, 0);  /* without header */
    2217         compressed_len = stored_len << 3;
    2218         *file_method = STORED;
    2219 
    2220     } else if (stored_len + 4 <= opt_lenb && buf != (char *) 0) {
     1634        G2.compressed_len = stored_len << 3;
     1635
     1636    } else if (stored_len + 4 <= opt_lenb && buf != NULL) {
    22211637        /* 4: two words for the lengths */
    22221638        /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
    … …  
    22271643         */
    22281644        send_bits((STORED_BLOCK << 1) + eof, 3);    /* send block type */
    2229         compressed_len = (compressed_len + 3 + 7) & ~7L;
    2230         compressed_len += (stored_len + 4) << 3;
     1645        G2.compressed_len = (G2.compressed_len + 3 + 7) & ~7L;
     1646        G2.compressed_len += (stored_len + 4) << 3;
    22311647
    22321648        copy_block(buf, (unsigned) stored_len, 1);  /* with header */
    … …  
    22341650    } else if (static_lenb == opt_lenb) {
    22351651        send_bits((STATIC_TREES << 1) + eof, 3);
    2236         compress_block((ct_data *) static_ltree, (ct_data *) static_dtree);
    2237         compressed_len += 3 + static_len;
     1652        compress_block((ct_data *) G2.static_ltree, (ct_data *) G2.static_dtree);
     1653        G2.compressed_len += 3 + G2.static_len;
    22381654    } else {
    22391655        send_bits((DYN_TREES << 1) + eof, 3);
    2240         send_all_trees(l_desc.max_code + 1, d_desc.max_code + 1,
     1656        send_all_trees(G2.l_desc.max_code + 1, G2.d_desc.max_code + 1,
    22411657                       max_blindex + 1);
    2242         compress_block((ct_data *) dyn_ltree, (ct_data *) dyn_dtree);
    2243         compressed_len += 3 + opt_len;
    2244     }
    2245     Assert(compressed_len == bits_sent, "bad compressed size");
     1658        compress_block((ct_data *) G2.dyn_ltree, (ct_data *) G2.dyn_dtree);
     1659        G2.compressed_len += 3 + G2.opt_len;
     1660    }
     1661    Assert(G2.compressed_len == G1.bits_sent, "bad compressed size");
    22461662    init_block();
    22471663
    22481664    if (eof) {
    22491665        bi_windup();
    2250         compressed_len += 7;    /* align on byte boundary */
    2251     }
    2252     Tracev((stderr, "\ncomprlen %lu(%lu) ", compressed_len >> 3,
    2253             compressed_len - 7 * eof));
    2254 
    2255     return compressed_len >> 3;
    2256 }
    2257 
    2258 /* ===========================================================================
    2259  * Save the match info and tally the frequency counts. Return true if
    2260  * the current block must be flushed.
    2261  */
    2262 static int ct_tally(int dist, int lc)
    2263 {
    2264     l_buf[last_lit++] = (uch) lc;
    2265     if (dist == 0) {
    2266         /* lc is the unmatched char */
    2267         dyn_ltree[lc].Freq++;
    2268     } else {
    2269         /* Here, lc is the match length - MIN_MATCH */
    2270         dist--;         /* dist = match distance - 1 */
    2271         Assert((ush) dist < (ush) MAX_DIST &&
    2272                (ush) lc <= (ush) (MAX_MATCH - MIN_MATCH) &&
    2273                (ush) d_code(dist) < (ush) D_CODES, "ct_tally: bad match");
    2274 
    2275         dyn_ltree[length_code[lc] + LITERALS + 1].Freq++;
    2276         dyn_dtree[d_code(dist)].Freq++;
    2277 
    2278         d_buf[last_dist++] = (ush) dist;
    2279         flags |= flag_bit;
    2280     }
    2281     flag_bit <<= 1;
    2282 
    2283     /* Output the flags if they fill a byte: */
    2284     if ((last_lit & 7) == 0) {
    2285         flag_buf[last_flags++] = flags;
    2286         flags = 0, flag_bit = 1;
    2287     }
    2288     /* Try to guess if it is profitable to stop the current block here */
    2289     if ((last_lit & 0xfff) == 0) {
    2290         /* Compute an upper bound for the compressed length */
    2291         ulg out_length = (ulg) last_lit * 8L;
    2292         ulg in_length = (ulg) strstart - block_start;
    2293         int dcode;
    2294 
    2295         for (dcode = 0; dcode < D_CODES; dcode++) {
    2296             out_length +=
    2297                 (ulg) dyn_dtree[dcode].Freq * (5L + extra_dbits[dcode]);
     1666        G2.compressed_len += 7; /* align on byte boundary */
     1667    }
     1668    Tracev((stderr, "\ncomprlen %lu(%lu) ", G2.compressed_len >> 3,
     1669            G2.compressed_len - 7 * eof));
     1670
     1671    return G2.compressed_len >> 3;
     1672}
     1673
     1674
     1675/* ===========================================================================
     1676 * Update a hash value with the given input byte
     1677 * IN  assertion: all calls to to UPDATE_HASH are made with consecutive
     1678 *    input characters, so that a running hash key can be computed from the
     1679 *    previous key instead of complete recalculation each time.
     1680 */
     1681#define UPDATE_HASH(h, c) (h = (((h)<<H_SHIFT) ^ (c)) & HASH_MASK)
     1682
     1683
     1684/* ===========================================================================
     1685 * Same as above, but achieves better compression. We use a lazy
     1686 * evaluation for matches: a match is finally adopted only if there is
     1687 * no better match at the next window position.
     1688 *
     1689 * Processes a new input file and return its compressed length. Sets
     1690 * the compressed length, crc, deflate flags and internal file
     1691 * attributes.
     1692 */
     1693
     1694/* Flush the current block, with given end-of-file flag.
     1695 * IN assertion: strstart is set to the end of the current match. */
     1696#define FLUSH_BLOCK(eof) \
     1697    flush_block( \
     1698        G1.block_start >= 0L \
     1699            ? (char*)&G1.window[(unsigned)G1.block_start] \
     1700            : (char*)NULL, \
     1701        (ulg)G1.strstart - G1.block_start, \
     1702        (eof) \
     1703    )
     1704
     1705/* Insert string s in the dictionary and set match_head to the previous head
     1706 * of the hash chain (the most recent string with same hash key). Return
     1707 * the previous length of the hash chain.
     1708 * IN  assertion: all calls to to INSERT_STRING are made with consecutive
     1709 *    input characters and the first MIN_MATCH bytes of s are valid
     1710 *    (except for the last MIN_MATCH-1 bytes of the input file). */
     1711#define INSERT_STRING(s, match_head) \
     1712do { \
     1713    UPDATE_HASH(G1.ins_h, G1.window[(s) + MIN_MATCH-1]); \
     1714    G1.prev[(s) & WMASK] = match_head = head[G1.ins_h]; \
     1715    head[G1.ins_h] = (s); \
     1716} while (0)
     1717
     1718static ulg deflate(void)
     1719{
     1720    IPos hash_head;     /* head of hash chain */
     1721    IPos prev_match;    /* previous match */
     1722    int flush;          /* set if current block must be flushed */
     1723    int match_available = 0;    /* set if previous match exists */
     1724    unsigned match_length = MIN_MATCH - 1;  /* length of best match */
     1725
     1726    /* Process the input block. */
     1727    while (G1.lookahead != 0) {
     1728        /* Insert the string window[strstart .. strstart+2] in the
     1729         * dictionary, and set hash_head to the head of the hash chain:
     1730         */
     1731        INSERT_STRING(G1.strstart, hash_head);
     1732
     1733        /* Find the longest match, discarding those <= prev_length.
     1734         */
     1735        G1.prev_length = match_length;
     1736        prev_match = G1.match_start;
     1737        match_length = MIN_MATCH - 1;
     1738
     1739        if (hash_head != 0 && G1.prev_length < max_lazy_match
     1740         && G1.strstart - hash_head <= MAX_DIST
     1741        ) {
     1742            /* To simplify the code, we prevent matches with the string
     1743             * of window index 0 (in particular we have to avoid a match
     1744             * of the string with itself at the start of the input file).
     1745             */
     1746            match_length = longest_match(hash_head);
     1747            /* longest_match() sets match_start */
     1748            if (match_length > G1.lookahead)
     1749                match_length = G1.lookahead;
     1750
     1751            /* Ignore a length 3 match if it is too distant: */
     1752            if (match_length == MIN_MATCH && G1.strstart - G1.match_start > TOO_FAR) {
     1753                /* If prev_match is also MIN_MATCH, G1.match_start is garbage
     1754                 * but we will ignore the current match anyway.
     1755                 */
     1756                match_length--;
     1757            }
    22981758        }
    2299         out_length >>= 3;
    2300         Trace((stderr,
    2301                "\nlast_lit %u, last_dist %u, in %ld, out ~%ld(%ld%%) ",
    2302                last_lit, last_dist, in_length, out_length,
    2303                100L - out_length * 100L / in_length));
    2304         if (last_dist < last_lit / 2 && out_length < in_length / 2)
    2305             return 1;
    2306     }
    2307     return (last_lit == LIT_BUFSIZE - 1 || last_dist == DIST_BUFSIZE);
    2308     /* We avoid equality with LIT_BUFSIZE because of wraparound at 64K
    2309      * on 16 bit machines and because stored blocks are restricted to
    2310      * 64K-1 bytes.
    2311      */
    2312 }
    2313 
    2314 /* ===========================================================================
    2315  * Send the block data compressed using the given Huffman trees
    2316  */
    2317 static void compress_block(ct_data * ltree, ct_data * dtree)
    2318 {
    2319     unsigned dist;      /* distance of matched string */
    2320     int lc;             /* match length or unmatched char (if dist == 0) */
    2321     unsigned lx = 0;    /* running index in l_buf */
    2322     unsigned dx = 0;    /* running index in d_buf */
    2323     unsigned fx = 0;    /* running index in flag_buf */
    2324     uch flag = 0;       /* current flags */
    2325     unsigned code;      /* the code to send */
    2326     int extra;          /* number of extra bits to send */
    2327 
    2328     if (last_lit != 0)
    2329         do {
    2330             if ((lx & 7) == 0)
    2331                 flag = flag_buf[fx++];
    2332             lc = l_buf[lx++];
    2333             if ((flag & 1) == 0) {
    2334                 send_code(lc, ltree);   /* send a literal byte */
    2335                 Tracecv(isgraph(lc), (stderr, " '%c' ", lc));
    2336             } else {
    2337                 /* Here, lc is the match length - MIN_MATCH */
    2338                 code = length_code[lc];
    2339                 send_code(code + LITERALS + 1, ltree);  /* send the length code */
    2340                 extra = extra_lbits[code];
    2341                 if (extra != 0) {
    2342                     lc -= base_length[code];
    2343                     send_bits(lc, extra);   /* send the extra length bits */
    2344                 }
    2345                 dist = d_buf[dx++];
    2346                 /* Here, dist is the match distance - 1 */
    2347                 code = d_code(dist);
    2348                 Assert(code < D_CODES, "bad d_code");
    2349 
    2350                 send_code(code, dtree); /* send the distance code */
    2351                 extra = extra_dbits[code];
    2352                 if (extra != 0) {
    2353                     dist -= base_dist[code];
    2354                     send_bits(dist, extra); /* send the extra distance bits */
    2355                 }
    2356             }           /* literal or match pair ? */
    2357             flag >>= 1;
    2358         } while (lx < last_lit);
    2359 
    2360     send_code(END_BLOCK, ltree);
    2361 }
    2362 
    2363 /* ===========================================================================
    2364  * Set the file type to ASCII or BINARY, using a crude approximation:
    2365  * binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise.
    2366  * IN assertion: the fields freq of dyn_ltree are set and the total of all
    2367  * frequencies does not exceed 64K (to fit in an int on 16 bit machines).
    2368  */
    2369 static void set_file_type(void)
    2370 {
    2371     int n = 0;
    2372     unsigned ascii_freq = 0;
    2373     unsigned bin_freq = 0;
    2374 
    2375     while (n < 7)
    2376         bin_freq += dyn_ltree[n++].Freq;
    2377     while (n < 128)
    2378         ascii_freq += dyn_ltree[n++].Freq;
    2379     while (n < LITERALS)
    2380         bin_freq += dyn_ltree[n++].Freq;
    2381     *file_type = bin_freq > (ascii_freq >> 2) ? BINARY : ASCII;
    2382     if (*file_type == BINARY && translate_eol) {
    2383         bb_error_msg("-l used on binary file");
    2384     }
    2385 }
    2386 
    2387 /* zip.c -- compress files to the gzip or pkzip format
    2388  * Copyright (C) 1992-1993 Jean-loup Gailly
    2389  * This is free software; you can redistribute it and/or modify it under the
    2390  * terms of the GNU General Public License, see the file COPYING.
    2391  */
    2392 
    2393 
    2394 static uint32_t crc;            /* crc on uncompressed file data */
    2395 static long header_bytes;   /* number of bytes in gzip header */
    2396 
    2397 static void put_long(ulg n)
    2398 {
    2399     put_short((n) & 0xffff);
    2400     put_short(((ulg) (n)) >> 16);
    2401 }
    2402 
    2403 /* put_header_byte is used for the compressed output
    2404  * - for the initial 4 bytes that can't overflow the buffer.
    2405  */
    2406 #define put_header_byte(c) {outbuf[outcnt++]=(uch)(c);}
     1759        /* If there was a match at the previous step and the current
     1760         * match is not better, output the previous match:
     1761         */
     1762        if (G1.prev_length >= MIN_MATCH && match_length <= G1.prev_length) {
     1763            check_match(G1.strstart - 1, prev_match, G1.prev_length);
     1764            flush = ct_tally(G1.strstart - 1 - prev_match, G1.prev_length - MIN_MATCH);
     1765
     1766            /* Insert in hash table all strings up to the end of the match.
     1767             * strstart-1 and strstart are already inserted.
     1768             */
     1769            G1.lookahead -= G1.prev_length - 1;
     1770            G1.prev_length -= 2;
     1771            do {
     1772                G1.strstart++;
     1773                INSERT_STRING(G1.strstart, hash_head);
     1774                /* strstart never exceeds WSIZE-MAX_MATCH, so there are
     1775                 * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
     1776                 * these bytes are garbage, but it does not matter since the
     1777                 * next lookahead bytes will always be emitted as literals.
     1778                 */
     1779            } while (--G1.prev_length != 0);
     1780            match_available = 0;
     1781            match_length = MIN_MATCH - 1;
     1782            G1.strstart++;
     1783            if (flush) {
     1784                FLUSH_BLOCK(0);
     1785                G1.block_start = G1.strstart;
     1786            }
     1787        } else if (match_available) {
     1788            /* If there was no match at the previous position, output a
     1789             * single literal. If there was a match but the current match
     1790             * is longer, truncate the previous match to a single literal.
     1791             */
     1792            Tracevv((stderr, "%c", G1.window[G1.strstart - 1]));
     1793            if (ct_tally(0, G1.window[G1.strstart - 1])) {
     1794                FLUSH_BLOCK(0);
     1795                G1.block_start = G1.strstart;
     1796            }
     1797            G1.strstart++;
     1798            G1.lookahead--;
     1799        } else {
     1800            /* There is no previous match to compare with, wait for
     1801             * the next step to decide.
     1802             */
     1803            match_available = 1;
     1804            G1.strstart++;
     1805            G1.lookahead--;
     1806        }
     1807        Assert(G1.strstart <= G1.isize && lookahead <= G1.isize, "a bit too far");
     1808
     1809        /* Make sure that we always have enough lookahead, except
     1810         * at the end of the input file. We need MAX_MATCH bytes
     1811         * for the next match, plus MIN_MATCH bytes to insert the
     1812         * string following the next match.
     1813         */
     1814        while (G1.lookahead < MIN_LOOKAHEAD && !G1.eofile)
     1815            fill_window();
     1816    }
     1817    if (match_available)
     1818        ct_tally(0, G1.window[G1.strstart - 1]);
     1819
     1820    return FLUSH_BLOCK(1);  /* eof */
     1821}
     1822
     1823
     1824/* ===========================================================================
     1825 * Initialize the bit string routines.
     1826 */
     1827static void bi_init(void)
     1828{
     1829    G1.bi_buf = 0;
     1830    G1.bi_valid = 0;
     1831#ifdef DEBUG
     1832    G1.bits_sent = 0L;
     1833#endif
     1834}
     1835
     1836
     1837/* ===========================================================================
     1838 * Initialize the "longest match" routines for a new file
     1839 */
     1840static void lm_init(ush * flagsp)
     1841{
     1842    unsigned j;
     1843
     1844    /* Initialize the hash table. */
     1845    memset(head, 0, HASH_SIZE * sizeof(*head));
     1846    /* prev will be initialized on the fly */
     1847
     1848    /* speed options for the general purpose bit flag */
     1849    *flagsp |= 2;   /* FAST 4, SLOW 2 */
     1850    /* ??? reduce max_chain_length for binary files */
     1851
     1852    G1.strstart = 0;
     1853    G1.block_start = 0L;
     1854
     1855    G1.lookahead = file_read(G1.window,
     1856            sizeof(int) <= 2 ? (unsigned) WSIZE : 2 * WSIZE);
     1857
     1858    if (G1.lookahead == 0 || G1.lookahead == (unsigned) -1) {
     1859        G1.eofile = 1;
     1860        G1.lookahead = 0;
     1861        return;
     1862    }
     1863    G1.eofile = 0;
     1864    /* Make sure that we always have enough lookahead. This is important
     1865     * if input comes from a device such as a tty.
     1866     */
     1867    while (G1.lookahead < MIN_LOOKAHEAD && !G1.eofile)
     1868        fill_window();
     1869
     1870    G1.ins_h = 0;
     1871    for (j = 0; j < MIN_MATCH - 1; j++)
     1872        UPDATE_HASH(G1.ins_h, G1.window[j]);
     1873    /* If lookahead < MIN_MATCH, ins_h is garbage, but this is
     1874     * not important since only literal bytes will be emitted.
     1875     */
     1876}
     1877
     1878
     1879/* ===========================================================================
     1880 * Allocate the match buffer, initialize the various tables and save the
     1881 * location of the internal file attribute (ascii/binary) and method
     1882 * (DEFLATE/STORE).
     1883 * One callsite in zip()
     1884 */
     1885static void ct_init(void)
     1886{
     1887    int n;              /* iterates over tree elements */
     1888    int length;         /* length value */
     1889    int code;           /* code value */
     1890    int dist;           /* distance index */
     1891
     1892    G2.compressed_len = 0L;
     1893
     1894#ifdef NOT_NEEDED
     1895    if (G2.static_dtree[0].Len != 0)
     1896        return;         /* ct_init already called */
     1897#endif
     1898
     1899    /* Initialize the mapping length (0..255) -> length code (0..28) */
     1900    length = 0;
     1901    for (code = 0; code < LENGTH_CODES - 1; code++) {
     1902        G2.base_length[code] = length;
     1903        for (n = 0; n < (1 << extra_lbits[code]); n++) {
     1904            G2.length_code[length++] = code;
     1905        }
     1906    }
     1907    Assert(length == 256, "ct_init: length != 256");
     1908    /* Note that the length 255 (match length 258) can be represented
     1909     * in two different ways: code 284 + 5 bits or code 285, so we
     1910     * overwrite length_code[255] to use the best encoding:
     1911     */
     1912    G2.length_code[length - 1] = code;
     1913
     1914    /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
     1915    dist = 0;
     1916    for (code = 0; code < 16; code++) {
     1917        G2.base_dist[code] = dist;
     1918        for (n = 0; n < (1 << extra_dbits[code]); n++) {
     1919            G2.dist_code[dist++] = code;
     1920        }
     1921    }
     1922    Assert(dist == 256, "ct_init: dist != 256");
     1923    dist >>= 7;         /* from now on, all distances are divided by 128 */
     1924    for (; code < D_CODES; code++) {
     1925        G2.base_dist[code] = dist << 7;
     1926        for (n = 0; n < (1 << (extra_dbits[code] - 7)); n++) {
     1927            G2.dist_code[256 + dist++] = code;
     1928        }
     1929    }
     1930    Assert(dist == 256, "ct_init: 256+dist != 512");
     1931
     1932    /* Construct the codes of the static literal tree */
     1933    /* already zeroed - it's in bss
     1934    for (n = 0; n <= MAX_BITS; n++)
     1935        G2.bl_count[n] = 0; */
     1936
     1937    n = 0;
     1938    while (n <= 143) {
     1939        G2.static_ltree[n++].Len = 8;
     1940        G2.bl_count[8]++;
     1941    }
     1942    while (n <= 255) {
     1943        G2.static_ltree[n++].Len = 9;
     1944        G2.bl_count[9]++;
     1945    }
     1946    while (n <= 279) {
     1947        G2.static_ltree[n++].Len = 7;
     1948        G2.bl_count[7]++;
     1949    }
     1950    while (n <= 287) {
     1951        G2.static_ltree[n++].Len = 8;
     1952        G2.bl_count[8]++;
     1953    }
     1954    /* Codes 286 and 287 do not exist, but we must include them in the
     1955     * tree construction to get a canonical Huffman tree (longest code
     1956     * all ones)
     1957     */
     1958    gen_codes((ct_data *) G2.static_ltree, L_CODES + 1);
     1959
     1960    /* The static distance tree is trivial: */
     1961    for (n = 0; n < D_CODES; n++) {
     1962        G2.static_dtree[n].Len = 5;
     1963        G2.static_dtree[n].Code = bi_reverse(n, 5);
     1964    }
     1965
     1966    /* Initialize the first block of the first file: */
     1967    init_block();
     1968}
     1969
    24071970
    24081971/* ===========================================================================
    24091972 * Deflate in to out.
    24101973 * IN assertions: the input and output buffers are cleared.
    2411  *   The variables time_stamp and save_orig_name are initialized.
    2412  */
    2413 static int zip(int in, int out)
    2414 {
    2415     uch my_flags = 0;   /* general purpose bit flags */
    2416     ush attr = 0;       /* ascii/binary flag */
    2417     ush deflate_flags = 0;  /* pkzip -es, -en or -ex equivalent */
    2418 
    2419     ifd = in;
    2420     ofd = out;
    2421     outcnt = 0;
     1974 */
     1975
     1976static void zip(ulg time_stamp)
     1977{
     1978    ush deflate_flags = 0;  /* pkzip -es, -en or -ex equivalent */
     1979
     1980    G1.outcnt = 0;
    24221981
    24231982    /* Write the header to the gzip file. See algorithm.doc for the format */
    2424 
    2425 
    2426     method = DEFLATED;
    2427     put_header_byte(GZIP_MAGIC[0]); /* magic header */
    2428     put_header_byte(GZIP_MAGIC[1]);
    2429     put_header_byte(DEFLATED);  /* compression method */
    2430 
    2431     put_header_byte(my_flags);  /* general flags */
    2432     put_long(time_stamp);
     1983    /* magic header for gzip files: 1F 8B */
     1984    /* compression method: 8 (DEFLATED) */
     1985    /* general flags: 0 */
     1986    put_32bit(0x00088b1f);
     1987    put_32bit(time_stamp);
    24331988
    24341989    /* Write deflated file to zip file */
    2435     crc = updcrc(0, 0);
    2436 
    2437     bi_init(out);
    2438     ct_init(&attr, &method);
     1990    G1.crc = ~0;
     1991
     1992    bi_init();
     1993    ct_init();
    24391994    lm_init(&deflate_flags);
    24401995
    2441     put_byte((uch) deflate_flags);  /* extra flags */
    2442     put_byte(OS_CODE);  /* OS identifier */
    2443 
    2444     header_bytes = (long) outcnt;
    2445 
    2446     (void) deflate();
     1996    put_8bit(deflate_flags);    /* extra flags */
     1997    put_8bit(3);    /* OS identifier = 3 (Unix) */
     1998
     1999    deflate();
    24472000
    24482001    /* Write the crc and uncompressed size */
    2449     put_long(crc);
    2450     put_long(isize);
    2451     header_bytes += 2 * sizeof(long);
     2002    put_32bit(~G1.crc);
     2003    put_32bit(G1.isize);
    24522004
    24532005    flush_outbuf();
    2454     return OK;
    2455 }
    2456 
    2457 
    2458 /* ===========================================================================
    2459  * Read a new buffer from the current input file, perform end-of-line
    2460  * translation, and update the crc and input file size.
    2461  * IN assertion: size >= 2 (for end-of-line translation)
    2462  */
    2463 static int file_read(char *buf, unsigned size)
    2464 {
    2465     unsigned len;
    2466 
    2467     Assert(insize == 0, "inbuf not empty");
    2468 
    2469     len = read(ifd, buf, size);
    2470     if (len == (unsigned) (-1) || len == 0)
    2471         return (int) len;
    2472 
    2473     crc = updcrc((uch *) buf, len);
    2474     isize += (ulg) len;
    2475     return (int) len;
    2476 }
    2477 
    2478 /* ===========================================================================
    2479  * Write the output buffer outbuf[0..outcnt-1] and update bytes_out.
    2480  * (used for the compressed data only)
    2481  */
    2482 static void flush_outbuf(void)
    2483 {
    2484     if (outcnt == 0)
    2485         return;
    2486 
    2487     write_buf(ofd, (char *) outbuf, outcnt);
    2488     outcnt = 0;
    2489 }
     2006}
     2007
     2008
     2009/* ======================================================================== */
     2010static
     2011char* make_new_name_gzip(char *filename)
     2012{
     2013    return xasprintf("%s.gz", filename);
     2014}
     2015
     2016static
     2017USE_DESKTOP(long long) int pack_gzip(void)
     2018{
     2019    struct stat s;
     2020
     2021    clear_bufs();
     2022    s.st_ctime = 0;
     2023    fstat(STDIN_FILENO, &s);
     2024    zip(s.st_ctime);
     2025    return 0;
     2026}
     2027
     2028int gzip_main(int argc, char **argv);
     2029int gzip_main(int argc, char **argv)
     2030{
     2031    unsigned opt;
     2032
     2033    /* Must match bbunzip's constants OPT_STDOUT, OPT_FORCE! */
     2034    opt = getopt32(argv, "cfv" USE_GUNZIP("d") "q123456789" );
     2035    option_mask32 &= 0x7; /* Clear -d, ignore -q, -0..9 */
     2036    //if (opt & 0x1) // -c
     2037    //if (opt & 0x2) // -f
     2038    //if (opt & 0x4) // -v
     2039#if ENABLE_GUNZIP /* gunzip_main may not be visible... */
     2040    if (opt & 0x8) { // -d
     2041        return gunzip_main(argc, argv);
     2042    }
     2043#endif
     2044    argv += optind;
     2045
     2046    PTR_TO_GLOBALS = xzalloc(sizeof(struct globals) + sizeof(struct globals2))
     2047            + sizeof(struct globals);
     2048    G2.l_desc.dyn_tree    = G2.dyn_ltree;
     2049    G2.l_desc.static_tree = G2.static_ltree;
     2050    G2.l_desc.extra_bits  = extra_lbits;
     2051    G2.l_desc.extra_base  = LITERALS + 1;
     2052    G2.l_desc.elems       = L_CODES;
     2053    G2.l_desc.max_length  = MAX_BITS;
     2054    //G2.l_desc.max_code    = 0;
     2055
     2056    G2.d_desc.dyn_tree    = G2.dyn_dtree;
     2057    G2.d_desc.static_tree = G2.static_dtree;
     2058    G2.d_desc.extra_bits  = extra_dbits;
     2059    //G2.d_desc.extra_base  = 0;
     2060    G2.d_desc.elems       = D_CODES;
     2061    G2.d_desc.max_length  = MAX_BITS;
     2062    //G2.d_desc.max_code    = 0;
     2063
     2064    G2.bl_desc.dyn_tree    = G2.bl_tree;
     2065    //G2.bl_desc.static_tree = NULL;
     2066    G2.bl_desc.extra_bits  = extra_blbits,
     2067    //G2.bl_desc.extra_base  = 0;
     2068    G2.bl_desc.elems       = BL_CODES;
     2069    G2.bl_desc.max_length  = MAX_BL_BITS;
     2070    //G2.bl_desc.max_code    = 0;
     2071
     2072    /* Allocate all global buffers (for DYN_ALLOC option) */
     2073    ALLOC(uch, G1.l_buf, INBUFSIZ);
     2074    ALLOC(uch, G1.outbuf, OUTBUFSIZ);
     2075    ALLOC(ush, G1.d_buf, DIST_BUFSIZE);
     2076    ALLOC(uch, G1.window, 2L * WSIZE);
     2077    ALLOC(ush, G1.prev, 1L << BITS);
     2078
     2079    /* Initialise the CRC32 table */
     2080    G1.crc_32_tab = crc32_filltable(NULL, 0);
     2081
     2082    return bbunpack(argv, make_new_name_gzip, pack_gzip);
     2083}
Note: See TracChangeset for help on using the changeset viewer.