"Fossies" - the Fresh Open Source Software Archive

Member "pigz-2.6/pigz.c" (6 Feb 2021, 178630 Bytes) of package /linux/privat/pigz-2.6.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "pigz.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 2.5_vs_2.6.

    1 /* pigz.c -- parallel implementation of gzip
    2  * Copyright (C) 2007-2021 Mark Adler
    3  * Version 2.6  6 Feb 2021  Mark Adler
    4  */
    5 
    6 /*
    7   This software is provided 'as-is', without any express or implied
    8   warranty. In no event will the author be held liable for any damages
    9   arising from the use of this software.
   10 
   11   Permission is granted to anyone to use this software for any purpose,
   12   including commercial applications, and to alter it and redistribute it
   13   freely, subject to the following restrictions:
   14 
   15   1. The origin of this software must not be misrepresented; you must not
   16      claim that you wrote the original software. If you use this software
   17      in a product, an acknowledgment in the product documentation would be
   18      appreciated but is not required.
   19   2. Altered source versions must be plainly marked as such, and must not be
   20      misrepresented as being the original software.
   21   3. This notice may not be removed or altered from any source distribution.
   22 
   23   Mark Adler
   24   madler@alumni.caltech.edu
   25 
   26  */
   27 
   28 /* Version history:
   29    1.0    17 Jan 2007  First version, pipe only
   30    1.1    28 Jan 2007  Avoid void * arithmetic (some compilers don't get that)
   31                        Add note about requiring zlib 1.2.3
   32                        Allow compression level 0 (no compression)
   33                        Completely rewrite parallelism -- add a write thread
   34                        Use deflateSetDictionary() to make use of history
   35                        Tune argument defaults to best performance on four cores
   36    1.2.1   1 Feb 2007  Add long command line options, add all gzip options
   37                        Add debugging options
   38    1.2.2  19 Feb 2007  Add list (--list) function
   39                        Process file names on command line, write .gz output
   40                        Write name and time in gzip header, set output file time
   41                        Implement all command line options except --recursive
   42                        Add --keep option to prevent deleting input files
   43                        Add thread tracing information with -vv used
   44                        Copy crc32_combine() from zlib (shared libraries issue)
   45    1.3    25 Feb 2007  Implement --recursive
   46                        Expand help to show all options
   47                        Show help if no arguments or output piping are provided
   48                        Process options in GZIP environment variable
   49                        Add progress indicator to write thread if --verbose
   50    1.4     4 Mar 2007  Add --independent to facilitate damaged file recovery
   51                        Reallocate jobs for new --blocksize or --processes
   52                        Do not delete original if writing to stdout
   53                        Allow --processes 1, which does no threading
   54                        Add NOTHREAD define to compile without threads
   55                        Incorporate license text from zlib in source code
   56    1.5    25 Mar 2007  Reinitialize jobs for new compression level
   57                        Copy attributes and owner from input file to output file
   58                        Add decompression and testing
   59                        Add -lt (or -ltv) to show all entries and proper lengths
   60                        Add decompression, testing, listing of LZW (.Z) files
   61                        Only generate and show trace log if DEBUG defined
   62                        Take "-" argument to mean read file from stdin
   63    1.6    30 Mar 2007  Add zlib stream compression (--zlib), and decompression
   64    1.7    29 Apr 2007  Decompress first entry of a zip file (if deflated)
   65                        Avoid empty deflate blocks at end of deflate stream
   66                        Show zlib check value (Adler-32) when listing
   67                        Don't complain when decompressing empty file
   68                        Warn about trailing junk for gzip and zlib streams
   69                        Make listings consistent, ignore gzip extra flags
   70                        Add zip stream compression (--zip)
   71    1.8    13 May 2007  Document --zip option in help output
   72    2.0    19 Oct 2008  Complete rewrite of thread usage and synchronization
   73                        Use polling threads and a pool of memory buffers
   74                        Remove direct pthread library use, hide in yarn.c
   75    2.0.1  20 Oct 2008  Check version of zlib at compile time, need >= 1.2.3
   76    2.1    24 Oct 2008  Decompress with read, write, inflate, and check threads
   77                        Remove spurious use of ctime_r(), ctime() more portable
   78                        Change application of job->calc lock to be a semaphore
   79                        Detect size of off_t at run time to select %lu vs. %llu
   80                        #define large file support macro even if not __linux__
   81                        Remove _LARGEFILE64_SOURCE, _FILE_OFFSET_BITS is enough
   82                        Detect file-too-large error and report, blame build
   83                        Replace check combination routines with those from zlib
   84    2.1.1  28 Oct 2008  Fix a leak for files with an integer number of blocks
   85                        Update for yarn 1.1 (yarn_prefix and yarn_abort)
   86    2.1.2  30 Oct 2008  Work around use of beta zlib in production systems
   87    2.1.3   8 Nov 2008  Don't use zlib combination routines, put back in pigz
   88    2.1.4   9 Nov 2008  Fix bug when decompressing very short files
   89    2.1.5  20 Jul 2009  Added 2008, 2009 to --license statement
   90                        Allow numeric parameter immediately after -p or -b
   91                        Enforce parameter after -p, -b, -s, before other options
   92                        Enforce numeric parameters to have only numeric digits
   93                        Try to determine the number of processors for -p default
   94                        Fix --suffix short option to be -S to match gzip [Bloch]
   95                        Decompress if executable named "unpigz" [Amundsen]
   96                        Add a little bit of testing to Makefile
   97    2.1.6  17 Jan 2010  Added pigz.spec to distribution for RPM systems [Brown]
   98                        Avoid some compiler warnings
   99                        Process symbolic links if piping to stdout [Hoffstätte]
  100                        Decompress if executable named "gunzip" [Hoffstätte]
  101                        Allow ".tgz" suffix [Chernookiy]
  102                        Fix adler32 comparison on .zz files
  103    2.1.7  17 Dec 2011  Avoid unused parameter warning in reenter()
  104                        Don't assume 2's complement ints in compress_thread()
  105                        Replicate gzip -cdf cat-like behavior
  106                        Replicate gzip -- option to suppress option decoding
  107                        Test output from make test instead of showing it
  108                        Updated pigz.spec to install unpigz, pigz.1 [Obermaier]
  109                        Add PIGZ environment variable [Mueller]
  110                        Replicate gzip suffix search when decoding or listing
  111                        Fix bug in load() to set in_left to zero on end of file
  112                        Do not check suffix when input file won't be modified
  113                        Decompress to stdout if name is "*cat" [Hayasaka]
  114                        Write data descriptor signature to be like Info-ZIP
  115                        Update and sort options list in help
  116                        Use CC variable for compiler in Makefile
  117                        Exit with code 2 if a warning has been issued
  118                        Fix thread synchronization problem when tracing
  119                        Change macro name MAX to MAX2 to avoid library conflicts
  120                        Determine number of processors on HP-UX [Lloyd]
  121    2.2    31 Dec 2011  Check for expansion bound busting (e.g. modified zlib)
  122                        Make the "threads" list head global variable volatile
  123                        Fix construction and printing of 32-bit check values
  124                        Add --rsyncable functionality
  125    2.2.1   1 Jan 2012  Fix bug in --rsyncable buffer management
  126    2.2.2   1 Jan 2012  Fix another bug in --rsyncable buffer management
  127    2.2.3  15 Jan 2012  Remove volatile in yarn.c
  128                        Reduce the number of input buffers
  129                        Change initial rsyncable hash to comparison value
  130                        Improve the efficiency of arriving at a byte boundary
  131                        Add thread portability #defines from yarn.c
  132                        Have rsyncable compression be independent of threading
  133                        Fix bug where constructed dictionaries not being used
  134    2.2.4  11 Mar 2012  Avoid some return value warnings
  135                        Improve the portability of printing the off_t type
  136                        Check for existence of compress binary before using
  137                        Update zlib version checking to 1.2.6 for new functions
  138                        Fix bug in zip (-K) output
  139                        Fix license in pigz.spec
  140                        Remove thread portability #defines in pigz.c
  141    2.2.5  28 Jul 2012  Avoid race condition in free_pool()
  142                        Change suffix to .tar when decompressing or listing .tgz
  143                        Print name of executable in error messages
  144                        Show help properly when the name is unpigz or gunzip
  145                        Fix permissions security problem before output is closed
  146    2.3     3 Mar 2013  Don't complain about missing suffix on stdout
  147                        Put all global variables in a structure for readability
  148                        Do not decompress concatenated zlib streams (just gzip)
  149                        Add option for compression level 11 to use zopfli
  150                        Fix handling of junk after compressed data
  151    2.3.1   9 Oct 2013  Fix builds of pigzt and pigzn to include zopfli
  152                        Add -lm, needed to link log function on some systems
  153                        Respect LDFLAGS in Makefile, use CFLAGS consistently
  154                        Add memory allocation tracking
  155                        Fix casting error in uncompressed length calculation
  156                        Update zopfli to Mar 10, 2013 Google state
  157                        Support zopfli in single thread case
  158                        Add -F, -I, -M, and -O options for zopfli tuning
  159    2.3.2  24 Jan 2015  Change whereis to which in Makefile for portability
  160                        Return zero exit code when only warnings are issued
  161                        Increase speed of unlzw (Unix compress decompression)
  162                        Update zopfli to current google state
  163                        Allow larger maximum blocksize (-b), now 512 MiB
  164                        Do not require that -d precede -N, -n, -T options
  165                        Strip any path from header name for -dN or -dNT
  166                        Remove use of PATH_MAX (PATH_MAX is not reliable)
  167                        Do not abort on inflate data error, do remaining files
  168                        Check gzip header CRC if present
  169                        Improve decompression error detection and reporting
  170    2.3.3  24 Jan 2015  Portability improvements
  171                        Update copyright years in documentation
  172    2.3.4   1 Oct 2016  Fix an out of bounds access due to invalid LZW input
  173                        Add an extra sync marker between independent blocks
  174                        Add zlib version for verbose version option (-vV)
  175                        Permit named pipes as input (e.g. made by mkfifo())
  176                        Fix a bug in -r directory traversal
  177                        Add warning for a zip file entry 4 GiB or larger
  178    2.4    26 Dec 2017  Portability improvements
  179                        Produce Zip64 format when needed for --zip (>= 4 GiB)
  180                        Make -no-name compatible with gzip, add --time option
  181                        Add -m as a short option for --no-time
  182                        Check run-time zlib version to handle weak linking
  183                        Fix a concurrent read bug in --list operation
  184                        Process options first, for gzip compatibility
  185                        Add --synchronous (-Y) option to force device write
  186                        Disallow an empty suffix (e.g. --suffix '')
  187                        Return an exit code of 1 if any issues are encountered
  188                        Fix sign error in compression reduction percentage
  189    2.5    23 Jan 2021  Add --alias/-A option to set .zip name for stdin input
  190                        Add --comment/-C option to add comment in .gz or .zip
  191                        Fix a bug that misidentified a multi-entry .zip
  192                        Fix a bug that did not emit double syncs for -i -p 1
  193                        Fix a bug in yarn that could try to access freed data
  194                        Do not delete multi-entry .zip files when extracting
  195                        Do not reject .zip entries with bit 11 set
  196                        Avoid a possible threads lock-order inversion
  197                        Ignore trailing junk after a gzip stream by default
  198    2.6     6 Feb 2021  Add --huffman/-H and --rle/U strategy options
  199                        Fix issue when compiling for no threads
  200                        Fail silently on a broken pipe
  201  */
  202 
  203 #define VERSION "pigz 2.6"
  204 
  205 /* To-do:
  206     - make source portable for Windows, VMS, etc. (see gzip source code)
  207     - make build portable (currently good for Unixish)
  208  */
  209 
  210 /*
  211    pigz compresses using threads to make use of multiple processors and cores.
  212    The input is broken up into 128 KB chunks with each compressed in parallel.
  213    The individual check value for each chunk is also calculated in parallel.
  214    The compressed data is written in order to the output, and a combined check
  215    value is calculated from the individual check values.
  216 
  217    The compressed data format generated is in the gzip, zlib, or single-entry
  218    zip format using the deflate compression method. The compression produces
  219    partial raw deflate streams which are concatenated by a single write thread
  220    and wrapped with the appropriate header and trailer, where the trailer
  221    contains the combined check value.
  222 
  223    Each partial raw deflate stream is terminated by an empty stored block
  224    (using the Z_SYNC_FLUSH option of zlib), in order to end that partial bit
  225    stream at a byte boundary, unless that partial stream happens to already end
  226    at a byte boundary (the latter requires zlib 1.2.6 or later). Ending on a
  227    byte boundary allows the partial streams to be concatenated simply as
  228    sequences of bytes. This adds a very small four to five byte overhead
  229    (average 3.75 bytes) to the output for each input chunk.
  230 
  231    The default input block size is 128K, but can be changed with the -b option.
  232    The number of compress threads is set by default to 8, which can be changed
  233    using the -p option. Specifying -p 1 avoids the use of threads entirely.
  234    pigz will try to determine the number of processors in the machine, in which
  235    case if that number is two or greater, pigz will use that as the default for
  236    -p instead of 8.
  237 
  238    The input blocks, while compressed independently, have the last 32K of the
  239    previous block loaded as a preset dictionary to preserve the compression
  240    effectiveness of deflating in a single thread. This can be turned off using
  241    the --independent or -i option, so that the blocks can be decompressed
  242    independently for partial error recovery or for random access.
  243 
  244    Decompression can't be parallelized over an arbitrary number of processors
  245    like compression can be, at least not without specially prepared deflate
  246    streams for that purpose. As a result, pigz uses a single thread (the main
  247    thread) for decompression, but will create three other threads for reading,
  248    writing, and check calculation, which can speed up decompression under some
  249    circumstances. Parallel decompression can be turned off by specifying one
  250    process (-dp 1 or -tp 1).
  251 
  252    pigz requires zlib 1.2.1 or later to allow setting the dictionary when doing
  253    raw deflate. Since zlib 1.2.3 corrects security vulnerabilities in zlib
  254    version 1.2.1 and 1.2.2, conditionals check for zlib 1.2.3 or later during
  255    the compilation of pigz.c. zlib 1.2.4 includes some improvements to
  256    Z_FULL_FLUSH and deflateSetDictionary() that permit identical output for
  257    pigz with and without threads, which is not possible with zlib 1.2.3. This
  258    may be important for uses of pigz -R where small changes in the contents
  259    should result in small changes in the archive for rsync. Note that due to
  260    the details of how the lower levels of compression result in greater speed,
  261    compression level 3 and below does not permit identical pigz output with and
  262    without threads.
  263 
  264    pigz uses the POSIX pthread library for thread control and communication,
  265    through the yarn.h interface to yarn.c. yarn.c can be replaced with
  266    equivalent implementations using other thread libraries. pigz can be
  267    compiled with NOTHREAD #defined to not use threads at all (in which case
  268    pigz will not be able to live up to the "parallel" in its name).
  269  */
  270 
  271 /*
  272    Details of parallel compression implementation:
  273 
  274    When doing parallel compression, pigz uses the main thread to read the input
  275    in 'size' sized chunks (see -b), and puts those in a compression job list,
  276    each with a sequence number to keep track of the ordering. If it is not the
  277    first chunk, then that job also points to the previous input buffer, from
  278    which the last 32K will be used as a dictionary (unless -i is specified).
  279    This sets a lower limit of 32K on 'size'.
  280 
  281    pigz launches up to 'procs' compression threads (see -p). Each compression
  282    thread continues to look for jobs in the compression list and perform those
  283    jobs until instructed to return. When a job is pulled, the dictionary, if
  284    provided, will be loaded into the deflate engine and then that input buffer
  285    is dropped for reuse. Then the input data is compressed into an output
  286    buffer that grows in size if necessary to hold the compressed data. The job
  287    is then put into the write job list, sorted by the sequence number. The
  288    compress thread however continues to calculate the check value on the input
  289    data, either a CRC-32 or Adler-32, possibly in parallel with the write
  290    thread writing the output data. Once that's done, the compress thread drops
  291    the input buffer and also releases the lock on the check value so that the
  292    write thread can combine it with the previous check values. The compress
  293    thread has then completed that job, and goes to look for another.
  294 
  295    All of the compress threads are left running and waiting even after the last
  296    chunk is processed, so that they can support the next input to be compressed
  297    (more than one input file on the command line). Once pigz is done, it will
  298    call all the compress threads home (that'll do pig, that'll do).
  299 
  300    Before starting to read the input, the main thread launches the write thread
  301    so that it is ready pick up jobs immediately. The compress thread puts the
  302    write jobs in the list in sequence sorted order, so that the first job in
  303    the list is always has the lowest sequence number. The write thread waits
  304    for the next write job in sequence, and then gets that job. The job still
  305    holds its input buffer, from which the write thread gets the input buffer
  306    length for use in check value combination. Then the write thread drops that
  307    input buffer to allow its reuse. Holding on to the input buffer until the
  308    write thread starts also has the benefit that the read and compress threads
  309    can't get way ahead of the write thread and build up a large backlog of
  310    unwritten compressed data. The write thread will write the compressed data,
  311    drop the output buffer, and then wait for the check value to be unlocked by
  312    the compress thread. Then the write thread combines the check value for this
  313    chunk with the total check value for eventual use in the trailer. If this is
  314    not the last chunk, the write thread then goes back to look for the next
  315    output chunk in sequence. After the last chunk, the write thread returns and
  316    joins the main thread. Unlike the compress threads, a new write thread is
  317    launched for each input stream. The write thread writes the appropriate
  318    header and trailer around the compressed data.
  319 
  320    The input and output buffers are reused through their collection in pools.
  321    Each buffer has a use count, which when decremented to zero returns the
  322    buffer to the respective pool. Each input buffer has up to three parallel
  323    uses: as the input for compression, as the data for the check value
  324    calculation, and as a dictionary for compression. Each output buffer has
  325    only one use, which is as the output of compression followed serially as
  326    data to be written. The input pool is limited in the number of buffers, so
  327    that reading does not get way ahead of compression and eat up memory with
  328    more input than can be used. The limit is approximately two times the number
  329    of compression threads. In the case that reading is fast as compared to
  330    compression, that number allows a second set of buffers to be read while the
  331    first set of compressions are being performed. The number of output buffers
  332    is not directly limited, but is indirectly limited by the release of input
  333    buffers to about the same number.
  334  */
  335 
  336 // Portability defines.
  337 #define _FILE_OFFSET_BITS 64            // Use large file functions
  338 #define _LARGE_FILES                    // Same thing for AIX
  339 #define _XOPEN_SOURCE 700               // For POSIX 2008
  340 
  341 // Included headers and what is expected from each.
  342 #include <stdio.h>      // fflush(), fprintf(), fputs(), getchar(), putc(),
  343                         // puts(), printf(), vasprintf(), stderr, EOF, NULL,
  344                         // SEEK_END, size_t, off_t
  345 #include <stdlib.h>     // exit(), malloc(), free(), realloc(), atol(), atoi(),
  346                         // getenv()
  347 #include <stdarg.h>     // va_start(), va_arg(), va_end(), va_list
  348 #include <string.h>     // memset(), memchr(), memcpy(), strcmp(), strcpy(),
  349                         // strncpy(), strlen(), strcat(), strrchr(),
  350                         // strerror()
  351 #include <errno.h>      // errno, EEXIST
  352 #include <assert.h>     // assert()
  353 #include <time.h>       // ctime(), time(), time_t, mktime()
  354 #include <signal.h>     // signal(), SIGINT
  355 #include <sys/types.h>  // ssize_t
  356 #include <sys/stat.h>   // chmod(), stat(), fstat(), lstat(), struct stat,
  357                         // S_IFDIR, S_IFLNK, S_IFMT, S_IFREG
  358 #include <sys/time.h>   // utimes(), gettimeofday(), struct timeval
  359 #include <unistd.h>     // unlink(), _exit(), read(), write(), close(),
  360                         // lseek(), isatty(), chown(), fsync()
  361 #include <fcntl.h>      // open(), O_CREAT, O_EXCL, O_RDONLY, O_TRUNC,
  362                         // O_WRONLY, fcntl(), F_FULLFSYNC
  363 #include <dirent.h>     // opendir(), readdir(), closedir(), DIR,
  364                         // struct dirent
  365 #include <limits.h>     // UINT_MAX, INT_MAX
  366 #if __STDC_VERSION__-0 >= 199901L || __GNUC__-0 >= 3
  367 #  include <inttypes.h> // intmax_t, uintmax_t
  368    typedef uintmax_t length_t;
  369    typedef uint32_t crc_t;
  370 #else
  371    typedef unsigned long length_t;
  372    typedef unsigned long crc_t;
  373 #endif
  374 
  375 #ifdef PIGZ_DEBUG
  376 #  if defined(__APPLE__)
  377 #    include <malloc/malloc.h>
  378 #    define MALLOC_SIZE(p) malloc_size(p)
  379 #  elif defined (__linux)
  380 #    include <malloc.h>
  381 #    define MALLOC_SIZE(p) malloc_usable_size(p)
  382 #  elif defined (_WIN32) || defined(_WIN64)
  383 #    include <malloc.h>
  384 #    define MALLOC_SIZE(p) _msize(p)
  385 #  else
  386 #    define MALLOC_SIZE(p) (0)
  387 #  endif
  388 #endif
  389 
  390 #ifdef __hpux
  391 #  include <sys/param.h>
  392 #  include <sys/pstat.h>
  393 #endif
  394 
  395 #ifndef S_IFLNK
  396 #  define S_IFLNK 0
  397 #endif
  398 
  399 #ifdef __MINGW32__
  400 #  define chown(p,o,g) 0
  401 #  define utimes(p,t)  0
  402 #  define lstat(p,s)   stat(p,s)
  403 #  define _exit(s)     exit(s)
  404 #endif
  405 
  406 #include "zlib.h"       // deflateInit2(), deflateReset(), deflate(),
  407                         // deflateEnd(), deflateSetDictionary(), crc32(),
  408                         // adler32(), inflateBackInit(), inflateBack(),
  409                         // inflateBackEnd(), Z_DEFAULT_COMPRESSION,
  410                         // Z_DEFAULT_STRATEGY, Z_DEFLATED, Z_NO_FLUSH, Z_NULL,
  411                         // Z_OK, Z_SYNC_FLUSH, z_stream
  412 #if !defined(ZLIB_VERNUM) || ZLIB_VERNUM < 0x1230
  413 #  error "Need zlib version 1.2.3 or later"
  414 #endif
  415 
  416 #ifndef NOTHREAD
  417 #  include "yarn.h"     // thread, launch(), join(), join_all(), lock,
  418                         // new_lock(), possess(), twist(), wait_for(),
  419                         // release(), peek_lock(), free_lock(), yarn_name
  420 #endif
  421 
  422 #ifndef NOZOPFLI
  423 #  include "zopfli/src/zopfli/deflate.h"    // ZopfliDeflatePart(),
  424                                             // ZopfliInitOptions(),
  425                                             // ZopfliOptions
  426 #endif
  427 
  428 #include "try.h"        // try, catch, always, throw, drop, punt, ball_t
  429 
  430 // For local functions and globals.
  431 #define local static
  432 
  433 // Prevent end-of-line conversions on MSDOSish operating systems.
  434 #if defined(MSDOS) || defined(OS2) || defined(_WIN32) || defined(__CYGWIN__)
  435 #  include <io.h>       // setmode(), O_BINARY, _commit() for _WIN32
  436 #  define SET_BINARY_MODE(fd) setmode(fd, O_BINARY)
  437 #else
  438 #  define SET_BINARY_MODE(fd)
  439 #endif
  440 
  441 // Release an allocated pointer, if allocated, and mark as unallocated.
  442 #define RELEASE(ptr) \
  443     do { \
  444         if ((ptr) != NULL) { \
  445             FREE(ptr); \
  446             ptr = NULL; \
  447         } \
  448     } while (0)
  449 
  450 // Sliding dictionary size for deflate.
  451 #define DICT 32768U
  452 
  453 // Largest power of 2 that fits in an unsigned int. Used to limit requests to
  454 // zlib functions that use unsigned int lengths.
  455 #define MAXP2 (UINT_MAX - (UINT_MAX >> 1))
  456 
  457 /* rsyncable constants -- RSYNCBITS is the number of bits in the mask for
  458    comparison. For random input data, there will be a hit on average every
  459    1<<RSYNCBITS bytes. So for an RSYNCBITS of 12, there will be an average of
  460    one hit every 4096 bytes, resulting in a mean block size of 4096. RSYNCMASK
  461    is the resulting bit mask. RSYNCHIT is what the hash value is compared to
  462    after applying the mask.
  463 
  464    The choice of 12 for RSYNCBITS is consistent with the original rsyncable
  465    patch for gzip which also uses a 12-bit mask. This results in a relatively
  466    small hit to compression, on the order of 1.5% to 3%. A mask of 13 bits can
  467    be used instead if a hit of less than 1% to the compression is desired, at
  468    the expense of more blocks transmitted for rsync updates. (Your mileage may
  469    vary.)
  470 
  471    This implementation of rsyncable uses a different hash algorithm than what
  472    the gzip rsyncable patch uses in order to provide better performance in
  473    several regards. The algorithm is simply to shift the hash value left one
  474    bit and exclusive-or that with the next byte. This is masked to the number
  475    of hash bits (RSYNCMASK) and compared to all ones except for a zero in the
  476    top bit (RSYNCHIT). This rolling hash has a very small window of 19 bytes
  477    (RSYNCBITS+7). The small window provides the benefit of much more rapid
  478    resynchronization after a change, than does the 4096-byte window of the gzip
  479    rsyncable patch.
  480 
  481    The comparison value is chosen to avoid matching any repeated bytes or short
  482    sequences. The gzip rsyncable patch on the other hand uses a sum and zero
  483    for comparison, which results in certain bad behaviors, such as always
  484    matching everywhere in a long sequence of zeros. Such sequences occur
  485    frequently in tar files.
  486 
  487    This hash efficiently discards history older than 19 bytes simply by
  488    shifting that data past the top of the mask -- no history needs to be
  489    retained to undo its impact on the hash value, as is needed for a sum.
  490 
  491    The choice of the comparison value (RSYNCHIT) has the virtue of avoiding
  492    extremely short blocks. The shortest block is five bytes (RSYNCBITS-7) from
  493    hit to hit, and is unlikely. Whereas with the gzip rsyncable algorithm,
  494    blocks of one byte are not only possible, but in fact are the most likely
  495    block size.
  496 
  497    Thanks and acknowledgement to Kevin Day for his experimentation and insights
  498    on rsyncable hash characteristics that led to some of the choices here.
  499  */
  500 #define RSYNCBITS 12
  501 #define RSYNCMASK ((1U << RSYNCBITS) - 1)
  502 #define RSYNCHIT (RSYNCMASK >> 1)
  503 
  504 // Initial pool counts and sizes -- INBUFS is the limit on the number of input
  505 // spaces as a function of the number of processors (used to throttle the
  506 // creation of compression jobs), OUTPOOL is the initial size of the output
  507 // data buffer, chosen to make resizing of the buffer very unlikely and to
  508 // allow prepending with a dictionary for use as an input buffer for zopfli.
  509 #define INBUFS(p) (((p)<<1)+3)
  510 #define OUTPOOL(s) ((s)+((s)>>4)+DICT)
  511 
  512 // Input buffer size, and augmentation for re-inserting a central header.
  513 #define BUF 32768
  514 #define CEN 42
  515 #define EXT (BUF + CEN)     // provide enough room to unget a header
  516 
  517 // Globals (modified by main thread only when it's the only thread).
  518 local struct {
  519     int volatile ret;       // pigz return code
  520     char *prog;             // name by which pigz was invoked
  521     int ind;                // input file descriptor
  522     int outd;               // output file descriptor
  523     char *inf;              // input file name (allocated)
  524     size_t inz;             // input file name allocated size
  525     char *outf;             // output file name (allocated)
  526     int verbosity;          // 0 = quiet, 1 = normal, 2 = verbose, 3 = trace
  527     int headis;             // 1 to store name, 2 to store date, 3 both
  528     int pipeout;            // write output to stdout even if file
  529     int keep;               // true to prevent deletion of input file
  530     int force;              // true to overwrite, compress links, cat
  531     int sync;               // true to flush output file
  532     int form;               // gzip = 0, zlib = 1, zip = 2 or 3
  533     int magic1;             // first byte of possible header when decoding
  534     int recurse;            // true to dive down into directory structure
  535     char *sufx;             // suffix to use (".gz" or user supplied)
  536     char *name;             // name for gzip or zip header
  537     char *alias;            // name for zip header when input is stdin
  538     char *comment;          // comment for gzip or zip header.
  539     time_t mtime;           // time stamp from input file for gzip header
  540     int list;               // true to list files instead of compress
  541     int first;              // true if we need to print listing header
  542     int decode;             // 0 to compress, 1 to decompress, 2 to test
  543     int level;              // compression level
  544     int strategy;           // compression strategy
  545 #ifndef NOZOPFLI
  546     ZopfliOptions zopts;    // zopfli compression options
  547 #endif
  548     int rsync;              // true for rsync blocking
  549     int procs;              // maximum number of compression threads (>= 1)
  550     int setdict;            // true to initialize dictionary in each thread
  551     size_t block;           // uncompressed input size per thread (>= 32K)
  552 #ifndef NOTHREAD
  553     crc_t shift;            // pre-calculated CRC-32 shift for length block
  554 #endif
  555 
  556     // saved gzip/zip header data for decompression, testing, and listing
  557     time_t stamp;           // time stamp from gzip header
  558     char *hname;            // name from header (allocated)
  559     char *hcomm;            // comment from header (allocated)
  560     unsigned long zip_crc;  // local header crc
  561     length_t zip_clen;      // local header compressed length
  562     length_t zip_ulen;      // local header uncompressed length
  563     int zip64;              // true if has zip64 extended information
  564 
  565     // globals for decompression and listing buffered reading
  566     unsigned char in_buf[EXT];  // input buffer
  567     unsigned char *in_next; // next unused byte in buffer
  568     size_t in_left;         // number of unused bytes in buffer
  569     int in_eof;             // true if reached end of file on input
  570     int in_short;           // true if last read didn't fill buffer
  571     length_t in_tot;        // total bytes read from input
  572     length_t out_tot;       // total bytes written to output
  573     unsigned long out_check;    // check value of output
  574 
  575 #ifndef NOTHREAD
  576     // globals for decompression parallel reading
  577     unsigned char in_buf2[EXT]; // second buffer for parallel reads
  578     size_t in_len;          // data waiting in next buffer
  579     int in_which;           // -1: start, 0: in_buf2, 1: in_buf
  580     lock *load_state;       // value = 0 to wait, 1 to read a buffer
  581     thread *load_thread;    // load_read() thread for joining
  582 #endif
  583 } g;
  584 
  585 // Display a complaint with the program name on stderr.
  586 local int complain(char *fmt, ...) {
  587     va_list ap;
  588 
  589     if (g.verbosity > 0) {
  590         fprintf(stderr, "%s: ", g.prog);
  591         va_start(ap, fmt);
  592         vfprintf(stderr, fmt, ap);
  593         va_end(ap);
  594         putc('\n', stderr);
  595         fflush(stderr);
  596     }
  597     g.ret = 1;
  598     return 0;
  599 }
  600 
  601 #ifdef PIGZ_DEBUG
  602 
  603 // Memory tracking.
  604 
  605 #define MAXMEM 131072   // maximum number of tracked pointers
  606 
  607 local struct mem_track_s {
  608     size_t num;         // current number of allocations
  609     size_t size;        // total size of current allocations
  610     size_t tot;         // maximum number of allocations
  611     size_t max;         // maximum size of allocations
  612 #ifndef NOTHREAD
  613     lock *lock;         // lock for access across threads
  614 #endif
  615     size_t have;        // number in array (possibly != num)
  616     void *mem[MAXMEM];  // sorted array of allocated pointers
  617 } mem_track;
  618 
  619 #ifndef NOTHREAD
  620 #  define mem_track_grab(m) possess((m)->lock)
  621 #  define mem_track_drop(m) release((m)->lock)
  622 #else
  623 #  define mem_track_grab(m)
  624 #  define mem_track_drop(m)
  625 #endif
  626 
  627 // Return the leftmost insert location of ptr in the sorted list mem->mem[],
  628 // which currently has mem->have elements. If ptr is already in the list, the
  629 // returned value will point to its first occurrence. The return location will
  630 // be one after the last element if ptr is greater than all of the elements.
  631 local size_t search_track(struct mem_track_s *mem, void *ptr) {
  632     ptrdiff_t left = 0;
  633     ptrdiff_t right = mem->have - 1;
  634     while (left <= right) {
  635         ptrdiff_t mid = (left + right) >> 1;
  636         if (mem->mem[mid] < ptr)
  637             left = mid + 1;
  638         else
  639             right = mid - 1;
  640     }
  641     return left;
  642 }
  643 
  644 // Insert ptr in the sorted list mem->mem[] and update the memory allocation
  645 // statistics.
  646 local void insert_track(struct mem_track_s *mem, void *ptr) {
  647     mem_track_grab(mem);
  648     assert(mem->have < MAXMEM && "increase MAXMEM in source and try again");
  649     size_t i = search_track(mem, ptr);
  650     if (i < mem->have && mem->mem[i] == ptr)
  651         complain("mem_track: duplicate pointer %p\n", ptr);
  652     memmove(&mem->mem[i + 1], &mem->mem[i],
  653             (mem->have - i) * sizeof(void *));
  654     mem->mem[i] = ptr;
  655     mem->have++;
  656     mem->num++;
  657     mem->size += MALLOC_SIZE(ptr);
  658     if (mem->num > mem->tot)
  659         mem->tot = mem->num;
  660     if (mem->size > mem->max)
  661         mem->max = mem->size;
  662     mem_track_drop(mem);
  663 }
  664 
  665 // Find and delete ptr from the sorted list mem->mem[] and update the memory
  666 // allocation statistics.
  667 local void delete_track(struct mem_track_s *mem, void *ptr) {
  668     mem_track_grab(mem);
  669     size_t i = search_track(mem, ptr);
  670     if (i < mem->num && mem->mem[i] == ptr) {
  671         memmove(&mem->mem[i], &mem->mem[i + 1],
  672                 (mem->have - (i + 1)) * sizeof(void *));
  673         mem->have--;
  674     }
  675     else
  676         complain("mem_track: missing pointer %p\n", ptr);
  677     mem->num--;
  678     mem->size -= MALLOC_SIZE(ptr);
  679     mem_track_drop(mem);
  680 }
  681 
  682 local void *malloc_track(struct mem_track_s *mem, size_t size) {
  683     void *ptr = malloc(size);
  684     if (ptr != NULL)
  685         insert_track(mem, ptr);
  686     return ptr;
  687 }
  688 
  689 local void *realloc_track(struct mem_track_s *mem, void *ptr, size_t size) {
  690     if (ptr == NULL)
  691         return malloc_track(mem, size);
  692     delete_track(mem, ptr);
  693     void *got = realloc(ptr, size);
  694     insert_track(mem, got == NULL ? ptr : got);
  695     return got;
  696 }
  697 
  698 local void free_track(struct mem_track_s *mem, void *ptr) {
  699     if (ptr != NULL) {
  700         delete_track(mem, ptr);
  701         free(ptr);
  702     }
  703 }
  704 
  705 #ifndef NOTHREAD
  706 local void *yarn_malloc(size_t size) {
  707     return malloc_track(&mem_track, size);
  708 }
  709 
  710 local void yarn_free(void *ptr) {
  711     free_track(&mem_track, ptr);
  712 }
  713 #endif
  714 
  715 local voidpf zlib_alloc(voidpf opaque, uInt items, uInt size) {
  716     return malloc_track(opaque, items * (size_t)size);
  717 }
  718 
  719 local void zlib_free(voidpf opaque, voidpf address) {
  720     free_track(opaque, address);
  721 }
  722 
  723 #define REALLOC(p, s) realloc_track(&mem_track, p, s)
  724 #define FREE(p) free_track(&mem_track, p)
  725 #define OPAQUE (&mem_track)
  726 #define ZALLOC zlib_alloc
  727 #define ZFREE zlib_free
  728 
  729 #else // !PIGZ_DEBUG
  730 
  731 #define REALLOC realloc
  732 #define FREE free
  733 #define OPAQUE Z_NULL
  734 #define ZALLOC Z_NULL
  735 #define ZFREE Z_NULL
  736 
  737 #endif
  738 
  739 // Assured memory allocation.
  740 local void *alloc(void *ptr, size_t size) {
  741     ptr = REALLOC(ptr, size);
  742     if (ptr == NULL)
  743         throw(ENOMEM, "not enough memory");
  744     return ptr;
  745 }
  746 
  747 #ifdef PIGZ_DEBUG
  748 
  749 // Logging.
  750 
  751 // Starting time of day for tracing.
  752 local struct timeval start;
  753 
  754 // Trace log.
  755 local struct log {
  756     struct timeval when;    // time of entry
  757     char *msg;              // message
  758     struct log *next;       // next entry
  759 } *log_head, **log_tail = NULL;
  760 #ifndef NOTHREAD
  761   local lock *log_lock = NULL;
  762 #endif
  763 
  764 // Maximum log entry length.
  765 #define MAXMSG 256
  766 
  767 // Set up log (call from main thread before other threads launched).
  768 local void log_init(void) {
  769     if (log_tail == NULL) {
  770         mem_track.num = 0;
  771         mem_track.size = 0;
  772         mem_track.num = 0;
  773         mem_track.max = 0;
  774         mem_track.have = 0;
  775 #ifndef NOTHREAD
  776         mem_track.lock = new_lock(0);
  777         yarn_mem(yarn_malloc, yarn_free);
  778         log_lock = new_lock(0);
  779 #endif
  780         log_head = NULL;
  781         log_tail = &log_head;
  782     }
  783 }
  784 
  785 // Add entry to trace log.
  786 local void log_add(char *fmt, ...) {
  787     struct timeval now;
  788     struct log *me;
  789     va_list ap;
  790     char msg[MAXMSG];
  791 
  792     gettimeofday(&now, NULL);
  793     me = alloc(NULL, sizeof(struct log));
  794     me->when = now;
  795     va_start(ap, fmt);
  796     vsnprintf(msg, MAXMSG, fmt, ap);
  797     va_end(ap);
  798     me->msg = alloc(NULL, strlen(msg) + 1);
  799     strcpy(me->msg, msg);
  800     me->next = NULL;
  801 #ifndef NOTHREAD
  802     assert(log_lock != NULL);
  803     possess(log_lock);
  804 #endif
  805     *log_tail = me;
  806     log_tail = &(me->next);
  807 #ifndef NOTHREAD
  808     twist(log_lock, BY, +1);
  809 #endif
  810 }
  811 
  812 // Pull entry from trace log and print it, return false if empty.
  813 local int log_show(void) {
  814     struct log *me;
  815     struct timeval diff;
  816 
  817     if (log_tail == NULL)
  818         return 0;
  819 #ifndef NOTHREAD
  820     possess(log_lock);
  821 #endif
  822     me = log_head;
  823     if (me == NULL) {
  824 #ifndef NOTHREAD
  825         release(log_lock);
  826 #endif
  827         return 0;
  828     }
  829     log_head = me->next;
  830     if (me->next == NULL)
  831         log_tail = &log_head;
  832 #ifndef NOTHREAD
  833     twist(log_lock, BY, -1);
  834 #endif
  835     diff.tv_usec = me->when.tv_usec - start.tv_usec;
  836     diff.tv_sec = me->when.tv_sec - start.tv_sec;
  837     if (diff.tv_usec < 0) {
  838         diff.tv_usec += 1000000L;
  839         diff.tv_sec--;
  840     }
  841     fprintf(stderr, "trace %ld.%06ld %s\n",
  842             (long)diff.tv_sec, (long)diff.tv_usec, me->msg);
  843     fflush(stderr);
  844     FREE(me->msg);
  845     FREE(me);
  846     return 1;
  847 }
  848 
  849 // Release log resources (need to do log_init() to use again).
  850 local void log_free(void) {
  851     struct log *me;
  852 
  853     if (log_tail != NULL) {
  854 #ifndef NOTHREAD
  855         possess(log_lock);
  856 #endif
  857         while ((me = log_head) != NULL) {
  858             log_head = me->next;
  859             FREE(me->msg);
  860             FREE(me);
  861         }
  862 #ifndef NOTHREAD
  863         twist(log_lock, TO, 0);
  864         free_lock(log_lock);
  865         log_lock = NULL;
  866         yarn_mem(malloc, free);
  867         free_lock(mem_track.lock);
  868 #endif
  869         log_tail = NULL;
  870     }
  871 }
  872 
  873 // Show entries until no more, free log.
  874 local void log_dump(void) {
  875     if (log_tail == NULL)
  876         return;
  877     while (log_show())
  878         ;
  879     log_free();
  880     if (mem_track.num || mem_track.size)
  881         complain("memory leak: %zu allocs of %zu bytes total",
  882                  mem_track.num, mem_track.size);
  883     if (mem_track.max)
  884         fprintf(stderr, "%zu bytes of memory used in %zu allocs\n",
  885                 mem_track.max, mem_track.tot);
  886 }
  887 
  888 // Debugging macro.
  889 #define Trace(x) \
  890     do { \
  891         if (g.verbosity > 2) { \
  892             log_add x; \
  893         } \
  894     } while (0)
  895 
  896 #else // !PIGZ_DEBUG
  897 
  898 #define log_dump()
  899 #define Trace(x)
  900 
  901 #endif
  902 
  903 // Abort or catch termination signal.
  904 local void cut_short(int sig) {
  905     if (sig == SIGINT) {
  906         Trace(("termination by user"));
  907     }
  908     if (g.outd != -1 && g.outd != 1) {
  909         unlink(g.outf);
  910         RELEASE(g.outf);
  911         g.outd = -1;
  912     }
  913     log_dump();
  914     _exit(sig < 0 ? -sig : EINTR);
  915 }
  916 
  917 // Common code for catch block of top routine in the thread.
  918 #define THREADABORT(ball) \
  919     do { \
  920         if ((ball).code != EPIPE) \
  921             complain("abort: %s", (ball).why); \
  922         drop(ball); \
  923         cut_short(-(ball).code); \
  924     } while (0)
  925 
  926 // Compute next size up by multiplying by about 2**(1/3) and rounding to the
  927 // next power of 2 if close (three applications results in doubling). If small,
  928 // go up to at least 16, if overflow, go to max size_t value.
  929 local inline size_t grow(size_t size) {
  930     size_t was, top;
  931     int shift;
  932 
  933     was = size;
  934     size += size >> 2;
  935     top = size;
  936     for (shift = 0; top > 7; shift++)
  937         top >>= 1;
  938     if (top == 7)
  939         size = (size_t)1 << (shift + 3);
  940     if (size < 16)
  941         size = 16;
  942     if (size <= was)
  943         size = (size_t)0 - 1;
  944     return size;
  945 }
  946 
  947 // Copy cpy[0..len-1] to *mem + off, growing *mem if necessary, where *size is
  948 // the allocated size of *mem. Return the number of bytes in the result.
  949 local inline size_t vmemcpy(char **mem, size_t *size, size_t off,
  950                             void *cpy, size_t len) {
  951     size_t need;
  952 
  953     need = off + len;
  954     if (need < off)
  955         throw(ERANGE, "overflow");
  956     if (need > *size) {
  957         need = grow(need);
  958         if (off == 0) {
  959             RELEASE(*mem);
  960             *size = 0;
  961         }
  962         *mem = alloc(*mem, need);
  963         *size = need;
  964     }
  965     memcpy(*mem + off, cpy, len);
  966     return off + len;
  967 }
  968 
  969 // Copy the zero-terminated string cpy to *str + off, growing *str if
  970 // necessary, where *size is the allocated size of *str. Return the length of
  971 // the string plus one.
  972 local inline size_t vstrcpy(char **str, size_t *size, size_t off, void *cpy) {
  973     return vmemcpy(str, size, off, cpy, strlen(cpy) + 1);
  974 }
  975 
  976 // Read up to len bytes into buf, repeating read() calls as needed.
  977 local size_t readn(int desc, unsigned char *buf, size_t len) {
  978     ssize_t ret;
  979     size_t got;
  980 
  981     got = 0;
  982     while (len) {
  983         ret = read(desc, buf, len);
  984         if (ret < 0)
  985             throw(errno, "read error on %s (%s)", g.inf, strerror(errno));
  986         if (ret == 0)
  987             break;
  988         buf += ret;
  989         len -= (size_t)ret;
  990         got += (size_t)ret;
  991     }
  992     return got;
  993 }
  994 
  995 // Write len bytes, repeating write() calls as needed. Return len.
  996 local size_t writen(int desc, void const *buf, size_t len) {
  997     char const *next = buf;
  998     size_t left = len;
  999 
 1000     while (left) {
 1001         size_t const max = SSIZE_MAX;
 1002         ssize_t ret = write(desc, next, left > max ? max : left);
 1003         if (ret < 1)
 1004             throw(errno, "write error on %s (%s)", g.outf, strerror(errno));
 1005         next += ret;
 1006         left -= (size_t)ret;
 1007     }
 1008     return len;
 1009 }
 1010 
 1011 // Convert Unix time to MS-DOS date and time, assuming the current timezone.
 1012 // (You got a better idea?)
 1013 local unsigned long time2dos(time_t t) {
 1014     struct tm *tm;
 1015     unsigned long dos;
 1016 
 1017     if (t == 0)
 1018         t = time(NULL);
 1019     tm = localtime(&t);
 1020     if (tm->tm_year < 80 || tm->tm_year > 207)
 1021         return 0;
 1022     dos = (unsigned long)(tm->tm_year - 80) << 25;
 1023     dos += (unsigned long)(tm->tm_mon + 1) << 21;
 1024     dos += (unsigned long)tm->tm_mday << 16;
 1025     dos += (unsigned long)tm->tm_hour << 11;
 1026     dos += (unsigned long)tm->tm_min << 5;
 1027     dos += (unsigned long)(tm->tm_sec + 1) >> 1;    // round to even seconds
 1028     return dos;
 1029 }
 1030 
 1031 // Value type for put() value arguments. All value arguments for put() must be
 1032 // cast to this type in order for va_arg() to pull the correct type from the
 1033 // argument list.
 1034 typedef length_t val_t;
 1035 
 1036 // Write a set of header or trailer values to out, which is a file descriptor.
 1037 // The values are specified by a series of arguments in pairs, where the first
 1038 // argument in each pair is the number of bytes, and the second argument in
 1039 // each pair is the unsigned integer value to write. The first argument in each
 1040 // pair must be an int, and the second argument in each pair must be a val_t.
 1041 // The arguments are terminated by a single zero (an int). If the number of
 1042 // bytes is positive, then the value is written in little-endian order. If the
 1043 // number of bytes is negative, then the value is written in big-endian order.
 1044 // The total number of bytes written is returned. This makes the long and
 1045 // tiresome zip format headers and trailers more readable, maintainable, and
 1046 // verifiable.
 1047 local unsigned put(int out, ...) {
 1048     // compute the total number of bytes
 1049     unsigned count = 0;
 1050     int n;
 1051     va_list ap;
 1052     va_start(ap, out);
 1053     while ((n = va_arg(ap, int)) != 0) {
 1054         va_arg(ap, val_t);
 1055         count += (unsigned)abs(n);
 1056     }
 1057     va_end(ap);
 1058 
 1059     // allocate memory for the data
 1060     unsigned char *wrap = alloc(NULL, count);
 1061     unsigned char *next = wrap;
 1062 
 1063     // write the requested data to wrap[]
 1064     va_start(ap, out);
 1065     while ((n = va_arg(ap, int)) != 0) {
 1066         val_t val = va_arg(ap, val_t);
 1067         if (n < 0) {            // big endian
 1068             n = -n << 3;
 1069             do {
 1070                 n -= 8;
 1071                 *next++ = (unsigned char)(val >> n);
 1072             } while (n);
 1073         }
 1074         else                    // little endian
 1075             do {
 1076                 *next++ = (unsigned char)val;
 1077                 val >>= 8;
 1078             } while (--n);
 1079     }
 1080     va_end(ap);
 1081 
 1082     // write wrap[] to out and return the number of bytes written
 1083     writen(out, wrap, count);
 1084     FREE(wrap);
 1085     return count;
 1086 }
 1087 
 1088 // Low 32-bits set to all ones.
 1089 #define LOW32 0xffffffff
 1090 
 1091 // Write a gzip, zlib, or zip header using the information in the globals.
 1092 local length_t put_header(void) {
 1093     length_t len;
 1094 
 1095     if (g.form > 1) {               // zip
 1096         // write local header -- we don't know yet whether the lengths will fit
 1097         // in 32 bits or not, so we have to assume that they might not and put
 1098         // in a Zip64 extra field so that the data descriptor that appears
 1099         // after the compressed data is interpreted with 64-bit lengths
 1100         len = put(g.outd,
 1101             4, (val_t)0x04034b50,   // local header signature
 1102             2, (val_t)45,           // version needed to extract (4.5)
 1103             2, (val_t)8,            // flags: data descriptor follows data
 1104             2, (val_t)8,            // deflate
 1105             4, (val_t)time2dos(g.mtime),
 1106             4, (val_t)0,            // crc (not here)
 1107             4, (val_t)LOW32,        // compressed length (not here)
 1108             4, (val_t)LOW32,        // uncompressed length (not here)
 1109             2, (val_t)(strlen(g.name == NULL ? g.alias : g.name)),  // name len
 1110             2, (val_t)29,           // length of extra field (see below)
 1111             0);
 1112 
 1113         // write file name (use g.alias for stdin)
 1114         len += writen(g.outd, g.name == NULL ? g.alias : g.name,
 1115                       strlen(g.name == NULL ? g.alias : g.name));
 1116 
 1117         // write Zip64 and extended timestamp extra field blocks (29 bytes)
 1118         len += put(g.outd,
 1119             2, (val_t)0x0001,       // Zip64 extended information ID
 1120             2, (val_t)16,           // number of data bytes in this block
 1121             8, (val_t)0,            // uncompressed length (not here)
 1122             8, (val_t)0,            // compressed length (not here)
 1123             2, (val_t)0x5455,       // extended timestamp ID
 1124             2, (val_t)5,            // number of data bytes in this block
 1125             1, (val_t)1,            // flag presence of mod time
 1126             4, (val_t)g.mtime,      // mod time
 1127             0);
 1128     }
 1129     else if (g.form) {              // zlib
 1130         if (g.comment != NULL)
 1131             complain("can't store comment in zlib format -- ignoring");
 1132         unsigned head;
 1133         head = (0x78 << 8) +        // deflate, 32K window
 1134                (g.level >= 9 ? 3 << 6 :
 1135                 g.level == 1 ? 0 << 6:
 1136                 g.level >= 6 || g.level == Z_DEFAULT_COMPRESSION ? 1 << 6 :
 1137                 2 << 6);            // optional compression level clue
 1138         head += 31 - (head % 31);   // make it a multiple of 31
 1139         len = put(g.outd,
 1140             -2, (val_t)head,        // zlib format uses big-endian order
 1141             0);
 1142     }
 1143     else {                          // gzip
 1144         len = put(g.outd,
 1145             1, (val_t)31,
 1146             1, (val_t)139,
 1147             1, (val_t)8,            // deflate
 1148             1, (val_t)((g.name != NULL ? 8 : 0) +
 1149                        (g.comment != NULL ? 16 : 0)),
 1150             4, (val_t)g.mtime,
 1151             1, (val_t)(g.level >= 9 ? 2 : g.level == 1 ? 4 : 0),
 1152             1, (val_t)3,            // unix
 1153             0);
 1154         if (g.name != NULL)
 1155             len += writen(g.outd, g.name, strlen(g.name) + 1);
 1156         if (g.comment != NULL)
 1157             len += writen(g.outd, g.comment, strlen(g.comment) + 1);
 1158     }
 1159     return len;
 1160 }
 1161 
 1162 // Write a gzip, zlib, or zip trailer.
 1163 local void put_trailer(length_t ulen, length_t clen,
 1164                        unsigned long check, length_t head) {
 1165     if (g.form > 1) {               // zip
 1166         // write Zip64 data descriptor, as promised in the local header
 1167         length_t desc = put(g.outd,
 1168             4, (val_t)0x08074b50,
 1169             4, (val_t)check,
 1170             8, (val_t)clen,
 1171             8, (val_t)ulen,
 1172             0);
 1173 
 1174         // zip64 is true if either the compressed or the uncompressed length
 1175         // does not fit in 32 bits, in which case there needs to be a Zip64
 1176         // extra block in the central directory entry
 1177         int zip64 = ulen >= LOW32 || clen >= LOW32;
 1178 
 1179         // write central file header
 1180         length_t cent = put(g.outd,
 1181             4, (val_t)0x02014b50,   // central header signature
 1182             1, (val_t)45,           // made by 4.5 for Zip64 V1 end record
 1183             1, (val_t)255,          // ignore external attributes
 1184             2, (val_t)45,           // version needed to extract (4.5)
 1185             2, (val_t)8,            // data descriptor is present
 1186             2, (val_t)8,            // deflate
 1187             4, (val_t)time2dos(g.mtime),
 1188             4, (val_t)check,        // crc
 1189             4, (val_t)(zip64 ? LOW32 : clen),   // compressed length
 1190             4, (val_t)(zip64 ? LOW32 : ulen),   // uncompressed length
 1191             2, (val_t)(strlen(g.name == NULL ? g.alias : g.name)),  // name len
 1192             2, (val_t)(zip64 ? 29 : 9), // extra field size (see below)
 1193             2, (val_t)(g.comment == NULL ? 0 : strlen(g.comment)),  // comment
 1194             2, (val_t)0,            // disk number 0
 1195             2, (val_t)0,            // internal file attributes
 1196             4, (val_t)0,            // external file attributes (ignored)
 1197             4, (val_t)0,            // offset of local header
 1198             0);
 1199 
 1200         // write file name (use g.alias for stdin)
 1201         cent += writen(g.outd, g.name == NULL ? g.alias : g.name,
 1202                        strlen(g.name == NULL ? g.alias : g.name));
 1203 
 1204         // write Zip64 extra field block (20 bytes)
 1205         if (zip64)
 1206             cent += put(g.outd,
 1207                 2, (val_t)0x0001,   // Zip64 extended information ID
 1208                 2, (val_t)16,       // number of data bytes in this block
 1209                 8, (val_t)ulen,     // uncompressed length
 1210                 8, (val_t)clen,     // compressed length
 1211                 0);
 1212 
 1213         // write extended timestamp extra field block (9 bytes)
 1214         cent += put(g.outd,
 1215             2, (val_t)0x5455,       // extended timestamp signature
 1216             2, (val_t)5,            // number of data bytes in this block
 1217             1, (val_t)1,            // flag presence of mod time
 1218             4, (val_t)g.mtime,      // mod time
 1219             0);
 1220 
 1221         // write comment, if requested
 1222         if (g.comment != NULL)
 1223             cent += writen(g.outd, g.comment, strlen(g.comment));
 1224 
 1225         // here zip64 is true if the offset of the central directory does not
 1226         // fit in 32 bits, in which case insert the Zip64 end records to
 1227         // provide a 64-bit offset
 1228         zip64 = head + clen + desc >= LOW32;
 1229         if (zip64) {
 1230             // write Zip64 end of central directory record and locator
 1231             put(g.outd,
 1232                 4, (val_t)0x06064b50,   // Zip64 end of central dir sig
 1233                 8, (val_t)44,       // size of the remainder of this record
 1234                 2, (val_t)45,       // version made by
 1235                 2, (val_t)45,       // version needed to extract
 1236                 4, (val_t)0,        // number of this disk
 1237                 4, (val_t)0,        // disk with start of central directory
 1238                 8, (val_t)1,        // number of entries on this disk
 1239                 8, (val_t)1,        // total number of entries
 1240                 8, (val_t)cent,     // size of central directory
 1241                 8, (val_t)(head + clen + desc), // central dir offset
 1242                 4, (val_t)0x07064b50,   // Zip64 end locator signature
 1243                 4, (val_t)0,        // disk with Zip64 end of central dir
 1244                 8, (val_t)(head + clen + desc + cent),  // location
 1245                 4, (val_t)1,        // total number of disks
 1246                 0);
 1247         }
 1248 
 1249         // write end of central directory record
 1250         put(g.outd,
 1251             4, (val_t)0x06054b50,   // end of central directory signature
 1252             2, (val_t)0,            // number of this disk
 1253             2, (val_t)0,            // disk with start of central directory
 1254             2, (val_t)(zip64 ? 0xffff : 1), // entries on this disk
 1255             2, (val_t)(zip64 ? 0xffff : 1), // total number of entries
 1256             4, (val_t)(zip64 ? LOW32 : cent),   // size of central directory
 1257             4, (val_t)(zip64 ? LOW32 : head + clen + desc), // offset
 1258             2, (val_t)0,            // no zip file comment
 1259             0);
 1260     }
 1261     else if (g.form)                // zlib
 1262         put(g.outd,
 1263             -4, (val_t)check,       // zlib format uses big-endian order
 1264             0);
 1265     else                            // gzip
 1266         put(g.outd,
 1267             4, (val_t)check,
 1268             4, (val_t)ulen,
 1269             0);
 1270 }
 1271 
 1272 // Compute an Adler-32, allowing a size_t length.
 1273 local unsigned long adler32z(unsigned long adler,
 1274                            unsigned char const *buf, size_t len) {
 1275     while (len > UINT_MAX && buf != NULL) {
 1276         adler = adler32(adler, buf, UINT_MAX);
 1277         buf += UINT_MAX;
 1278         len -= UINT_MAX;
 1279     }
 1280     return adler32(adler, buf, (unsigned)len);
 1281 }
 1282 
 1283 // Compute a CRC-32, allowing a size_t length.
 1284 local unsigned long crc32z(unsigned long crc,
 1285                            unsigned char const *buf, size_t len) {
 1286     while (len > UINT_MAX && buf != NULL) {
 1287         crc = crc32(crc, buf, UINT_MAX);
 1288         buf += UINT_MAX;
 1289         len -= UINT_MAX;
 1290     }
 1291     return crc32(crc, buf, (unsigned)len);
 1292 }
 1293 
 1294 // Compute check value depending on format.
 1295 #define CHECK(a,b,c) (g.form == 1 ? adler32z(a,b,c) : crc32z(a,b,c))
 1296 
 1297 // Return the zlib version as an integer, where each component is interpreted
 1298 // as a decimal number and converted to four hexadecimal digits. E.g.
 1299 // '1.2.11.1' -> 0x12b1, or return -1 if the string is not a valid version.
 1300 local long zlib_vernum(void) {
 1301     char const *ver = zlibVersion();
 1302     long num = 0;
 1303     int left = 4;
 1304     int comp = 0;
 1305     do {
 1306         if (*ver >= '0' && *ver <= '9')
 1307             comp = 10 * comp + *ver - '0';
 1308         else {
 1309             num = (num << 4) + (comp > 0xf ? 0xf : comp);
 1310             left--;
 1311             if (*ver != '.')
 1312                 break;
 1313             comp = 0;
 1314         }
 1315         ver++;
 1316     } while (left);
 1317     return left < 2 ? num << (left << 2) : -1;
 1318 }
 1319 
 1320 #ifndef NOTHREAD
 1321 // -- threaded portions of pigz --
 1322 
 1323 // -- check value combination routines for parallel calculation --
 1324 
 1325 #define COMB(a,b,c) (g.form == 1 ? adler32_comb(a,b,c) : crc32_comb(a,b,c))
 1326 // Combine two crc-32's or two adler-32's (copied from zlib 1.2.3 so that pigz
 1327 // can be compatible with older versions of zlib).
 1328 
 1329 // We copy the combination routines from zlib here, in order to avoid linkage
 1330 // issues with the zlib 1.2.3 builds on Sun, Ubuntu, and others.
 1331 
 1332 // CRC-32 polynomial, reflected.
 1333 #define POLY 0xedb88320
 1334 
 1335 // Return a(x) multiplied by b(x) modulo p(x), where p(x) is the CRC
 1336 // polynomial, reflected. For speed, this requires that a not be zero.
 1337 local crc_t multmodp(crc_t a, crc_t b) {
 1338     crc_t m = (crc_t)1 << 31;
 1339     crc_t p = 0;
 1340     for (;;) {
 1341         if (a & m) {
 1342             p ^= b;
 1343             if ((a & (m - 1)) == 0)
 1344                 break;
 1345         }
 1346         m >>= 1;
 1347         b = b & 1 ? (b >> 1) ^ POLY : b >> 1;
 1348     }
 1349     return p;
 1350 }
 1351 
 1352 // Table of x^2^n modulo p(x).
 1353 local const crc_t x2n_table[] = {
 1354     0x40000000, 0x20000000, 0x08000000, 0x00800000, 0x00008000,
 1355     0xedb88320, 0xb1e6b092, 0xa06a2517, 0xed627dae, 0x88d14467,
 1356     0xd7bbfe6a, 0xec447f11, 0x8e7ea170, 0x6427800e, 0x4d47bae0,
 1357     0x09fe548f, 0x83852d0f, 0x30362f1a, 0x7b5a9cc3, 0x31fec169,
 1358     0x9fec022a, 0x6c8dedc4, 0x15d6874d, 0x5fde7a4e, 0xbad90e37,
 1359     0x2e4e5eef, 0x4eaba214, 0xa8a472c0, 0x429a969e, 0x148d302a,
 1360     0xc40ba6d0, 0xc4e22c3c};
 1361 
 1362 // Return x^(n*2^k) modulo p(x).
 1363 local crc_t x2nmodp(size_t n, unsigned k) {
 1364     crc_t p = (crc_t)1 << 31;       // x^0 == 1
 1365     while (n) {
 1366         if (n & 1)
 1367             p = multmodp(x2n_table[k & 31], p);
 1368         n >>= 1;
 1369         k++;
 1370     }
 1371     return p;
 1372 }
 1373 
 1374 // This uses the pre-computed g.shift value most of the time. Only the last
 1375 // combination requires a new x2nmodp() calculation.
 1376 local unsigned long crc32_comb(unsigned long crc1, unsigned long crc2,
 1377                                size_t len2) {
 1378     return multmodp(len2 == g.block ? g.shift : x2nmodp(len2, 3), crc1) ^ crc2;
 1379 }
 1380 
 1381 #define BASE 65521U     // largest prime smaller than 65536
 1382 #define LOW16 0xffff    // mask lower 16 bits
 1383 
 1384 local unsigned long adler32_comb(unsigned long adler1, unsigned long adler2,
 1385                                  size_t len2) {
 1386     unsigned long sum1;
 1387     unsigned long sum2;
 1388     unsigned rem;
 1389 
 1390     // the derivation of this formula is left as an exercise for the reader
 1391     rem = (unsigned)(len2 % BASE);
 1392     sum1 = adler1 & LOW16;
 1393     sum2 = (rem * sum1) % BASE;
 1394     sum1 += (adler2 & LOW16) + BASE - 1;
 1395     sum2 += ((adler1 >> 16) & LOW16) + ((adler2 >> 16) & LOW16) + BASE - rem;
 1396     if (sum1 >= BASE) sum1 -= BASE;
 1397     if (sum1 >= BASE) sum1 -= BASE;
 1398     if (sum2 >= (BASE << 1)) sum2 -= (BASE << 1);
 1399     if (sum2 >= BASE) sum2 -= BASE;
 1400     return sum1 | (sum2 << 16);
 1401 }
 1402 
 1403 // -- pool of spaces for buffer management --
 1404 
 1405 // These routines manage a pool of spaces. Each pool specifies a fixed size
 1406 // buffer to be contained in each space. Each space has a use count, which when
 1407 // decremented to zero returns the space to the pool. If a space is requested
 1408 // from the pool and the pool is empty, a space is immediately created unless a
 1409 // specified limit on the number of spaces has been reached. Only if the limit
 1410 // is reached will it wait for a space to be returned to the pool. Each space
 1411 // knows what pool it belongs to, so that it can be returned.
 1412 
 1413 // A space (one buffer for each space).
 1414 struct space {
 1415     lock *use;              // use count -- return to pool when zero
 1416     unsigned char *buf;     // buffer of size size
 1417     size_t size;            // current size of this buffer
 1418     size_t len;             // for application usage (initially zero)
 1419     struct pool *pool;      // pool to return to
 1420     struct space *next;     // for pool linked list
 1421 };
 1422 
 1423 // Pool of spaces (one pool for each type needed).
 1424 struct pool {
 1425     lock *have;             // unused spaces available, lock for list
 1426     struct space *head;     // linked list of available buffers
 1427     size_t size;            // size of new buffers in this pool
 1428     int limit;              // number of new spaces allowed, or -1
 1429     int made;               // number of buffers made
 1430 };
 1431 
 1432 // Initialize a pool (pool structure itself provided, not allocated). The limit
 1433 // is the maximum number of spaces in the pool, or -1 to indicate no limit,
 1434 // i.e., to never wait for a buffer to return to the pool.
 1435 local void new_pool(struct pool *pool, size_t size, int limit) {
 1436     pool->have = new_lock(0);
 1437     pool->head = NULL;
 1438     pool->size = size;
 1439     pool->limit = limit;
 1440     pool->made = 0;
 1441 }
 1442 
 1443 // Get a space from a pool. The use count is initially set to one, so there is
 1444 // no need to call use_space() for the first use.
 1445 local struct space *get_space(struct pool *pool) {
 1446     struct space *space;
 1447 
 1448     // if can't create any more, wait for a space to show up
 1449     possess(pool->have);
 1450     if (pool->limit == 0)
 1451         wait_for(pool->have, NOT_TO_BE, 0);
 1452 
 1453     // if a space is available, pull it from the list and return it
 1454     if (pool->head != NULL) {
 1455         space = pool->head;
 1456         pool->head = space->next;
 1457         twist(pool->have, BY, -1);      // one less in pool
 1458         possess(space->use);
 1459         twist(space->use, TO, 1);       // initially one user
 1460         space->len = 0;
 1461         return space;
 1462     }
 1463 
 1464     // nothing available, don't want to wait, make a new space
 1465     assert(pool->limit != 0);
 1466     if (pool->limit > 0)
 1467         pool->limit--;
 1468     pool->made++;
 1469     release(pool->have);
 1470     space = alloc(NULL, sizeof(struct space));
 1471     space->use = new_lock(1);           // initially one user
 1472     space->buf = alloc(NULL, pool->size);
 1473     space->size = pool->size;
 1474     space->len = 0;
 1475     space->pool = pool;                 // remember the pool this belongs to
 1476     return space;
 1477 }
 1478 
 1479 // Increase the size of the buffer in space.
 1480 local void grow_space(struct space *space) {
 1481     size_t more;
 1482 
 1483     // compute next size up
 1484     more = grow(space->size);
 1485     if (more == space->size)
 1486         throw(ERANGE, "overflow");
 1487 
 1488     // reallocate the buffer
 1489     space->buf = alloc(space->buf, more);
 1490     space->size = more;
 1491 }
 1492 
 1493 // Increment the use count to require one more drop before returning this space
 1494 // to the pool.
 1495 local void use_space(struct space *space) {
 1496     long use;
 1497 
 1498     possess(space->use);
 1499     use = peek_lock(space->use);
 1500     assert(use != 0);
 1501     twist(space->use, BY, +1);
 1502 }
 1503 
 1504 // Drop a space, returning it to the pool if the use count is zero.
 1505 local void drop_space(struct space *space) {
 1506     long use;
 1507     struct pool *pool;
 1508 
 1509     if (space == NULL)
 1510         return;
 1511     possess(space->use);
 1512     use = peek_lock(space->use);
 1513     assert(use != 0);
 1514     twist(space->use, BY, -1);
 1515     if (use == 1) {
 1516         pool = space->pool;
 1517         possess(pool->have);
 1518         space->next = pool->head;
 1519         pool->head = space;
 1520         twist(pool->have, BY, +1);
 1521     }
 1522 }
 1523 
 1524 // Free the memory and lock resources of a pool. Return number of spaces for
 1525 // debugging and resource usage measurement.
 1526 local int free_pool(struct pool *pool) {
 1527     int count;
 1528     struct space *space;
 1529 
 1530     possess(pool->have);
 1531     count = 0;
 1532     while ((space = pool->head) != NULL) {
 1533         pool->head = space->next;
 1534         FREE(space->buf);
 1535         free_lock(space->use);
 1536         FREE(space);
 1537         count++;
 1538     }
 1539     assert(count == pool->made);
 1540     release(pool->have);
 1541     free_lock(pool->have);
 1542     return count;
 1543 }
 1544 
 1545 // Input and output buffer pools.
 1546 local struct pool in_pool;
 1547 local struct pool out_pool;
 1548 local struct pool dict_pool;
 1549 local struct pool lens_pool;
 1550 
 1551 // -- parallel compression --
 1552 
 1553 // Compress or write job (passed from compress list to write list). If seq is
 1554 // equal to -1, compress_thread is instructed to return; if more is false then
 1555 // this is the last chunk, which after writing tells write_thread to return.
 1556 struct job {
 1557     long seq;                   // sequence number
 1558     int more;                   // true if this is not the last chunk
 1559     struct space *in;           // input data to compress
 1560     struct space *out;          // dictionary or resulting compressed data
 1561     struct space *lens;         // coded list of flush block lengths
 1562     unsigned long check;        // check value for input data
 1563     lock *calc;                 // released when check calculation complete
 1564     struct job *next;           // next job in the list (either list)
 1565 };
 1566 
 1567 // List of compress jobs (with tail for appending to list).
 1568 local lock *compress_have = NULL;   // number of compress jobs waiting
 1569 local struct job *compress_head, **compress_tail;
 1570 
 1571 // List of write jobs.
 1572 local lock *write_first;            // lowest sequence number in list
 1573 local struct job *write_head;
 1574 
 1575 // Number of compression threads running.
 1576 local int cthreads = 0;
 1577 
 1578 // Write thread if running.
 1579 local thread *writeth = NULL;
 1580 
 1581 // Setup job lists (call from main thread).
 1582 local void setup_jobs(void) {
 1583     // set up only if not already set up
 1584     if (compress_have != NULL)
 1585         return;
 1586 
 1587     // allocate locks and initialize lists
 1588     compress_have = new_lock(0);
 1589     compress_head = NULL;
 1590     compress_tail = &compress_head;
 1591     write_first = new_lock(-1);
 1592     write_head = NULL;
 1593 
 1594     // initialize buffer pools (initial size for out_pool not critical, since
 1595     // buffers will be grown in size if needed -- the initial size chosen to
 1596     // make this unlikely, the same for lens_pool)
 1597     new_pool(&in_pool, g.block, INBUFS(g.procs));
 1598     new_pool(&out_pool, OUTPOOL(g.block), -1);
 1599     new_pool(&dict_pool, DICT, -1);
 1600     new_pool(&lens_pool, g.block >> (RSYNCBITS - 1), -1);
 1601 }
 1602 
 1603 // Command the compress threads to all return, then join them all (call from
 1604 // main thread), free all the thread-related resources.
 1605 local void finish_jobs(void) {
 1606     struct job job;
 1607     int caught;
 1608 
 1609     // only do this once
 1610     if (compress_have == NULL)
 1611         return;
 1612 
 1613     // command all of the extant compress threads to return
 1614     possess(compress_have);
 1615     job.seq = -1;
 1616     job.next = NULL;
 1617     compress_head = &job;
 1618     compress_tail = &(job.next);
 1619     twist(compress_have, BY, +1);       // will wake them all up
 1620 
 1621     // join all of the compress threads, verify they all came back
 1622     caught = join_all();
 1623     Trace(("-- joined %d compress threads", caught));
 1624     assert(caught == cthreads);
 1625     cthreads = 0;
 1626 
 1627     // free the resources
 1628     caught = free_pool(&lens_pool);
 1629     Trace(("-- freed %d block lengths buffers", caught));
 1630     caught = free_pool(&dict_pool);
 1631     Trace(("-- freed %d dictionary buffers", caught));
 1632     caught = free_pool(&out_pool);
 1633     Trace(("-- freed %d output buffers", caught));
 1634     caught = free_pool(&in_pool);
 1635     Trace(("-- freed %d input buffers", caught));
 1636     free_lock(write_first);
 1637     free_lock(compress_have);
 1638     compress_have = NULL;
 1639 }
 1640 
 1641 // Compress all strm->avail_in bytes at strm->next_in to out->buf, updating
 1642 // out->len, grow the size of the buffer (out->size) if necessary. Respect the
 1643 // size limitations of the zlib stream data types (size_t may be larger than
 1644 // unsigned).
 1645 local void deflate_engine(z_stream *strm, struct space *out, int flush) {
 1646     size_t room;
 1647 
 1648     do {
 1649         room = out->size - out->len;
 1650         if (room == 0) {
 1651             grow_space(out);
 1652             room = out->size - out->len;
 1653         }
 1654         strm->next_out = out->buf + out->len;
 1655         strm->avail_out = room < UINT_MAX ? (unsigned)room : UINT_MAX;
 1656         (void)deflate(strm, flush);
 1657         out->len = (size_t)(strm->next_out - out->buf);
 1658     } while (strm->avail_out == 0);
 1659     assert(strm->avail_in == 0);
 1660 }
 1661 
 1662 // Get the next compression job from the head of the list, compress and compute
 1663 // the check value on the input, and put a job in the write list with the
 1664 // results. Keep looking for more jobs, returning when a job is found with a
 1665 // sequence number of -1 (leave that job in the list for other incarnations to
 1666 // find).
 1667 local void compress_thread(void *dummy) {
 1668     struct job *job;                // job pulled and working on
 1669     struct job *here, **prior;      // pointers for inserting in write list
 1670     unsigned long check;            // check value of input
 1671     unsigned char *next;            // pointer for blocks, check value data
 1672     size_t left;                    // input left to process
 1673     size_t len;                     // remaining bytes to compress/check
 1674 #if ZLIB_VERNUM >= 0x1260
 1675     int bits;                       // deflate pending bits
 1676 #endif
 1677     int ret;                        // zlib return code
 1678     ball_t err;                     // error information from throw()
 1679 
 1680     (void)dummy;
 1681 
 1682     try {
 1683         z_stream strm;                  // deflate stream
 1684 #ifndef NOZOPFLI
 1685         struct space *temp = NULL;
 1686         // get temporary space for zopfli input
 1687         if (g.level > 9)
 1688             temp = get_space(&out_pool);
 1689         else
 1690 #endif
 1691         {
 1692             // initialize the deflate stream for this thread
 1693             strm.zfree = ZFREE;
 1694             strm.zalloc = ZALLOC;
 1695             strm.opaque = OPAQUE;
 1696             ret = deflateInit2(&strm, 6, Z_DEFLATED, -15, 8, g.strategy);
 1697             if (ret == Z_MEM_ERROR)
 1698                 throw(ENOMEM, "not enough memory");
 1699             if (ret != Z_OK)
 1700                 throw(EINVAL, "internal error");
 1701         }
 1702 
 1703         // keep looking for work
 1704         for (;;) {
 1705             // get a job (like I tell my son)
 1706             possess(compress_have);
 1707             wait_for(compress_have, NOT_TO_BE, 0);
 1708             job = compress_head;
 1709             assert(job != NULL);
 1710             if (job->seq == -1)
 1711                 break;
 1712             compress_head = job->next;
 1713             if (job->next == NULL)
 1714                 compress_tail = &compress_head;
 1715             twist(compress_have, BY, -1);
 1716 
 1717             // got a job -- initialize and set the compression level (note that
 1718             // if deflateParams() is called immediately after deflateReset(),
 1719             // there is no need to initialize input/output for the stream)
 1720             Trace(("-- compressing #%ld", job->seq));
 1721 #ifndef NOZOPFLI
 1722             if (g.level <= 9) {
 1723 #endif
 1724                 (void)deflateReset(&strm);
 1725                 (void)deflateParams(&strm, g.level, g.strategy);
 1726 #ifndef NOZOPFLI
 1727             }
 1728             else
 1729                 temp->len = 0;
 1730 #endif
 1731 
 1732             // set dictionary if provided, release that input or dictionary
 1733             // buffer (not NULL if g.setdict is true and if this is not the
 1734             // first work unit)
 1735             if (job->out != NULL) {
 1736                 len = job->out->len;
 1737                 left = len < DICT ? len : DICT;
 1738 #ifndef NOZOPFLI
 1739                 if (g.level <= 9)
 1740 #endif
 1741                     deflateSetDictionary(&strm, job->out->buf + (len - left),
 1742                                          (unsigned)left);
 1743 #ifndef NOZOPFLI
 1744                 else {
 1745                     memcpy(temp->buf, job->out->buf + (len - left), left);
 1746                     temp->len = left;
 1747                 }
 1748 #endif
 1749                 drop_space(job->out);
 1750             }
 1751 
 1752             // set up input and output
 1753             job->out = get_space(&out_pool);
 1754 #ifndef NOZOPFLI
 1755             if (g.level <= 9) {
 1756 #endif
 1757                 strm.next_in = job->in->buf;
 1758                 strm.next_out = job->out->buf;
 1759 #ifndef NOZOPFLI
 1760             }
 1761             else
 1762                 memcpy(temp->buf + temp->len, job->in->buf, job->in->len);
 1763 #endif
 1764 
 1765             // compress each block, either flushing or finishing
 1766             next = job->lens == NULL ? NULL : job->lens->buf;
 1767             left = job->in->len;
 1768             job->out->len = 0;
 1769             do {
 1770                 // decode next block length from blocks list
 1771                 len = next == NULL ? 128 : *next++;
 1772                 if (len < 128)                  // 64..32831
 1773                     len = (len << 8) + (*next++) + 64;
 1774                 else if (len == 128)            // end of list
 1775                     len = left;
 1776                 else if (len < 192)             // 1..63
 1777                     len &= 0x3f;
 1778                 else if (len < 224){            // 32832..2129983
 1779                     len = ((len & 0x1f) << 16) + ((size_t)*next++ << 8);
 1780                     len += *next++ + 32832U;
 1781                 }
 1782                 else {                          // 2129984..539000895
 1783                     len = ((len & 0x1f) << 24) + ((size_t)*next++ << 16);
 1784                     len += (size_t)*next++ << 8;
 1785                     len += (size_t)*next++ + 2129984UL;
 1786                 }
 1787                 left -= len;
 1788 
 1789 #ifndef NOZOPFLI
 1790                 if (g.level <= 9) {
 1791 #endif
 1792                     // run MAXP2-sized amounts of input through deflate -- this
 1793                     // loop is needed for those cases where the unsigned type
 1794                     // is smaller than the size_t type, or when len is close to
 1795                     // the limit of the size_t type
 1796                     while (len > MAXP2) {
 1797                         strm.avail_in = MAXP2;
 1798                         deflate_engine(&strm, job->out, Z_NO_FLUSH);
 1799                         len -= MAXP2;
 1800                     }
 1801 
 1802                     // run the last piece through deflate -- end on a byte
 1803                     // boundary, using a sync marker if necessary, or finish
 1804                     // the deflate stream if this is the last block
 1805                     strm.avail_in = (unsigned)len;
 1806                     if (left || job->more) {
 1807 #if ZLIB_VERNUM >= 0x1260
 1808                         if (zlib_vernum() >= 0x1260) {
 1809                             deflate_engine(&strm, job->out, Z_BLOCK);
 1810 
 1811                             // add enough empty blocks to get to a byte
 1812                             // boundary
 1813                             (void)deflatePending(&strm, Z_NULL, &bits);
 1814                             if ((bits & 1) || !g.setdict)
 1815                                 deflate_engine(&strm, job->out, Z_SYNC_FLUSH);
 1816                             else if (bits & 7) {
 1817                                 do {        // add static empty blocks
 1818                                     bits = deflatePrime(&strm, 10, 2);
 1819                                     assert(bits == Z_OK);
 1820                                     (void)deflatePending(&strm, Z_NULL, &bits);
 1821                                 } while (bits & 7);
 1822                                 deflate_engine(&strm, job->out, Z_BLOCK);
 1823                             }
 1824                         }
 1825                         else
 1826 #endif
 1827                         {
 1828                             deflate_engine(&strm, job->out, Z_SYNC_FLUSH);
 1829                         }
 1830                         if (!g.setdict)     // two markers when independent
 1831                             deflate_engine(&strm, job->out, Z_FULL_FLUSH);
 1832                     }
 1833                     else
 1834                         deflate_engine(&strm, job->out, Z_FINISH);
 1835 #ifndef NOZOPFLI
 1836                 }
 1837                 else {
 1838                     // compress len bytes using zopfli, end at byte boundary
 1839                     unsigned char bits, *out;
 1840                     size_t outsize;
 1841 
 1842                     out = NULL;
 1843                     outsize = 0;
 1844                     bits = 0;
 1845                     ZopfliDeflatePart(&g.zopts, 2, !(left || job->more),
 1846                                       temp->buf, temp->len, temp->len + len,
 1847                                       &bits, &out, &outsize);
 1848                     assert(job->out->len + outsize + 5 <= job->out->size);
 1849                     memcpy(job->out->buf + job->out->len, out, outsize);
 1850                     free(out);
 1851                     job->out->len += outsize;
 1852                     if (left || job->more) {
 1853                         bits &= 7;
 1854                         if ((bits & 1) || !g.setdict) {
 1855                             if (bits == 0 || bits > 5)
 1856                                 job->out->buf[job->out->len++] = 0;
 1857                             job->out->buf[job->out->len++] = 0;
 1858                             job->out->buf[job->out->len++] = 0;
 1859                             job->out->buf[job->out->len++] = 0xff;
 1860                             job->out->buf[job->out->len++] = 0xff;
 1861                         }
 1862                         else if (bits) {
 1863                             do {
 1864                                 job->out->buf[job->out->len - 1] += 2 << bits;
 1865                                 job->out->buf[job->out->len++] = 0;
 1866                                 bits += 2;
 1867                             } while (bits < 8);
 1868                         }
 1869                         if (!g.setdict) {   // two markers when independent
 1870                             job->out->buf[job->out->len++] = 0;
 1871                             job->out->buf[job->out->len++] = 0;
 1872                             job->out->buf[job->out->len++] = 0;
 1873                             job->out->buf[job->out->len++] = 0xff;
 1874                             job->out->buf[job->out->len++] = 0xff;
 1875                         }
 1876                     }
 1877                     temp->len += len;
 1878                 }
 1879 #endif
 1880             } while (left);
 1881             drop_space(job->lens);
 1882             job->lens = NULL;
 1883             Trace(("-- compressed #%ld%s", job->seq,
 1884                    job->more ? "" : " (last)"));
 1885 
 1886             // reserve input buffer until check value has been calculated
 1887             use_space(job->in);
 1888 
 1889             // insert write job in list in sorted order, alert write thread
 1890             possess(write_first);
 1891             prior = &write_head;
 1892             while ((here = *prior) != NULL) {
 1893                 if (here->seq > job->seq)
 1894                     break;
 1895                 prior = &(here->next);
 1896             }
 1897             job->next = here;
 1898             *prior = job;
 1899             twist(write_first, TO, write_head->seq);
 1900 
 1901             // calculate the check value in parallel with writing, alert the
 1902             // write thread that the calculation is complete, and drop this
 1903             // usage of the input buffer
 1904             len = job->in->len;
 1905             next = job->in->buf;
 1906             check = CHECK(0L, Z_NULL, 0);
 1907             while (len > MAXP2) {
 1908                 check = CHECK(check, next, MAXP2);
 1909                 len -= MAXP2;
 1910                 next += MAXP2;
 1911             }
 1912             check = CHECK(check, next, (unsigned)len);
 1913             drop_space(job->in);
 1914             job->check = check;
 1915             Trace(("-- checked #%ld%s", job->seq, job->more ? "" : " (last)"));
 1916             possess(job->calc);
 1917             twist(job->calc, TO, 1);
 1918 
 1919             // done with that one -- go find another job
 1920         }
 1921 
 1922         // found job with seq == -1 -- return to join
 1923         release(compress_have);
 1924 #ifndef NOZOPFLI
 1925         if (g.level > 9)
 1926             drop_space(temp);
 1927         else
 1928 #endif
 1929         {
 1930             (void)deflateEnd(&strm);
 1931         }
 1932     }
 1933     catch (err) {
 1934         THREADABORT(err);
 1935     }
 1936 }
 1937 
 1938 // Collect the write jobs off of the list in sequence order and write out the
 1939 // compressed data until the last chunk is written. Also write the header and
 1940 // trailer and combine the individual check values of the input buffers.
 1941 local void write_thread(void *dummy) {
 1942     long seq;                       // next sequence number looking for
 1943     struct job *job;                // job pulled and working on
 1944     size_t len;                     // input length
 1945     int more;                       // true if more chunks to write
 1946     length_t head;                  // header length
 1947     length_t ulen;                  // total uncompressed size (overflow ok)
 1948     length_t clen;                  // total compressed size (overflow ok)
 1949     unsigned long check;            // check value of uncompressed data
 1950     ball_t err;                     // error information from throw()
 1951 
 1952     (void)dummy;
 1953 
 1954     try {
 1955         // build and write header
 1956         Trace(("-- write thread running"));
 1957         head = put_header();
 1958 
 1959         // process output of compress threads until end of input
 1960         ulen = clen = 0;
 1961         check = CHECK(0L, Z_NULL, 0);
 1962         seq = 0;
 1963         do {
 1964             // get next write job in order
 1965             possess(write_first);
 1966             wait_for(write_first, TO_BE, seq);
 1967             job = write_head;
 1968             write_head = job->next;
 1969             twist(write_first, TO, write_head == NULL ? -1 : write_head->seq);
 1970 
 1971             // update lengths, save uncompressed length for COMB
 1972             more = job->more;
 1973             len = job->in->len;
 1974             drop_space(job->in);
 1975             ulen += len;
 1976             clen += job->out->len;
 1977 
 1978             // write the compressed data and drop the output buffer
 1979             Trace(("-- writing #%ld", seq));
 1980             writen(g.outd, job->out->buf, job->out->len);
 1981             drop_space(job->out);
 1982             Trace(("-- wrote #%ld%s", seq, more ? "" : " (last)"));
 1983 
 1984             // wait for check calculation to complete, then combine, once the
 1985             // compress thread is done with the input, release it
 1986             possess(job->calc);
 1987             wait_for(job->calc, TO_BE, 1);
 1988             release(job->calc);
 1989             check = COMB(check, job->check, len);
 1990             Trace(("-- combined #%ld%s", seq, more ? "" : " (last)"));
 1991 
 1992             // free the job
 1993             free_lock(job->calc);
 1994             FREE(job);
 1995 
 1996             // get the next buffer in sequence
 1997             seq++;
 1998         } while (more);
 1999 
 2000         // write trailer
 2001         put_trailer(ulen, clen, check, head);
 2002 
 2003         // verify no more jobs, prepare for next use
 2004         possess(compress_have);
 2005         assert(compress_head == NULL && peek_lock(compress_have) == 0);
 2006         release(compress_have);
 2007         possess(write_first);
 2008         assert(write_head == NULL);
 2009         twist(write_first, TO, -1);
 2010     }
 2011     catch (err) {
 2012         THREADABORT(err);
 2013     }
 2014 }
 2015 
 2016 // Encode a hash hit to the block lengths list. hit == 0 ends the list.
 2017 local void append_len(struct job *job, size_t len) {
 2018     struct space *lens;
 2019 
 2020     assert(len < 539000896UL);
 2021     if (job->lens == NULL)
 2022         job->lens = get_space(&lens_pool);
 2023     lens = job->lens;
 2024     if (lens->size < lens->len + 3)
 2025         grow_space(lens);
 2026     if (len < 64)
 2027         lens->buf[lens->len++] = (unsigned char)(len + 128);
 2028     else if (len < 32832U) {
 2029         len -= 64;
 2030         lens->buf[lens->len++] = (unsigned char)(len >> 8);
 2031         lens->buf[lens->len++] = (unsigned char)len;
 2032     }
 2033     else if (len < 2129984UL) {
 2034         len -= 32832U;
 2035         lens->buf[lens->len++] = (unsigned char)((len >> 16) + 192);
 2036         lens->buf[lens->len++] = (unsigned char)(len >> 8);
 2037         lens->buf[lens->len++] = (unsigned char)len;
 2038     }
 2039     else {
 2040         len -= 2129984UL;
 2041         lens->buf[lens->len++] = (unsigned char)((len >> 24) + 224);
 2042         lens->buf[lens->len++] = (unsigned char)(len >> 16);
 2043         lens->buf[lens->len++] = (unsigned char)(len >> 8);
 2044         lens->buf[lens->len++] = (unsigned char)len;
 2045     }
 2046 }
 2047 
 2048 // Compress ind to outd, using multiple threads for the compression and check
 2049 // value calculations and one other thread for writing the output. Compress
 2050 // threads will be launched and left running (waiting actually) to support
 2051 // subsequent calls of parallel_compress().
 2052 local void parallel_compress(void) {
 2053     long seq;                       // sequence number
 2054     struct space *curr;             // input data to compress
 2055     struct space *next;             // input data that follows curr
 2056     struct space *hold;             // input data that follows next
 2057     struct space *dict;             // dictionary for next compression
 2058     struct job *job;                // job for compress, then write
 2059     int more;                       // true if more input to read
 2060     unsigned hash;                  // hash for rsyncable
 2061     unsigned char *scan;            // next byte to compute hash on
 2062     unsigned char *end;             // after end of data to compute hash on
 2063     unsigned char *last;            // position after last hit
 2064     size_t left;                    // last hit in curr to end of curr
 2065     size_t len;                     // for various length computations
 2066 
 2067     // if first time or after an option change, setup the job lists
 2068     setup_jobs();
 2069 
 2070     // start write thread
 2071     writeth = launch(write_thread, NULL);
 2072 
 2073     // read from input and start compress threads (write thread will pick up
 2074     // the output of the compress threads)
 2075     seq = 0;
 2076     next = get_space(&in_pool);
 2077     next->len = readn(g.ind, next->buf, next->size);
 2078     hold = NULL;
 2079     dict = NULL;
 2080     scan = next->buf;
 2081     hash = RSYNCHIT;
 2082     left = 0;
 2083     do {
 2084         // create a new job
 2085         job = alloc(NULL, sizeof(struct job));
 2086         job->calc = new_lock(0);
 2087 
 2088         // update input spaces
 2089         curr = next;
 2090         next = hold;
 2091         hold = NULL;
 2092 
 2093         // get more input if we don't already have some
 2094         if (next == NULL) {
 2095             next = get_space(&in_pool);
 2096             next->len = readn(g.ind, next->buf, next->size);
 2097         }
 2098 
 2099         // if rsyncable, generate block lengths and prepare curr for job to
 2100         // likely have less than size bytes (up to the last hash hit)
 2101         job->lens = NULL;
 2102         if (g.rsync && curr->len) {
 2103             // compute the hash function starting where we last left off to
 2104             // cover either size bytes or to EOF, whichever is less, through
 2105             // the data in curr (and in the next loop, through next) -- save
 2106             // the block lengths resulting from the hash hits in the job->lens
 2107             // list
 2108             if (left == 0) {
 2109                 // scan is in curr
 2110                 last = curr->buf;
 2111                 end = curr->buf + curr->len;
 2112                 while (scan < end) {
 2113                     hash = ((hash << 1) ^ *scan++) & RSYNCMASK;
 2114                     if (hash == RSYNCHIT) {
 2115                         len = (size_t)(scan - last);
 2116                         append_len(job, len);
 2117                         last = scan;
 2118                     }
 2119                 }
 2120 
 2121                 // continue scan in next
 2122                 left = (size_t)(scan - last);
 2123                 scan = next->buf;
 2124             }
 2125 
 2126             // scan in next for enough bytes to fill curr, or what is available
 2127             // in next, whichever is less (if next isn't full, then we're at
 2128             // the end of the file) -- the bytes in curr since the last hit,
 2129             // stored in left, counts towards the size of the first block
 2130             last = next->buf;
 2131             len = curr->size - curr->len;
 2132             if (len > next->len)
 2133                 len = next->len;
 2134             end = next->buf + len;
 2135             while (scan < end) {
 2136                 hash = ((hash << 1) ^ *scan++) & RSYNCMASK;
 2137                 if (hash == RSYNCHIT) {
 2138                     len = (size_t)(scan - last) + left;
 2139                     left = 0;
 2140                     append_len(job, len);
 2141                     last = scan;
 2142                 }
 2143             }
 2144             append_len(job, 0);
 2145 
 2146             // create input in curr for job up to last hit or entire buffer if
 2147             // no hits at all -- save remainder in next and possibly hold
 2148             len = (size_t)((job->lens->len == 1 ? scan : last) - next->buf);
 2149             if (len) {
 2150                 // got hits in next, or no hits in either -- copy to curr
 2151                 memcpy(curr->buf + curr->len, next->buf, len);
 2152                 curr->len += len;
 2153                 memmove(next->buf, next->buf + len, next->len - len);
 2154                 next->len -= len;
 2155                 scan -= len;
 2156                 left = 0;
 2157             }
 2158             else if (job->lens->len != 1 && left && next->len) {
 2159                 // had hits in curr, but none in next, and last hit in curr
 2160                 // wasn't right at the end, so we have input there to save --
 2161                 // use curr up to the last hit, save the rest, moving next to
 2162                 // hold
 2163                 hold = next;
 2164                 next = get_space(&in_pool);
 2165                 memcpy(next->buf, curr->buf + (curr->len - left), left);
 2166                 next->len = left;
 2167                 curr->len -= left;
 2168             }
 2169             else {
 2170                 // else, last match happened to be right at the end of curr, or
 2171                 // we're at the end of the input compressing the rest
 2172                 left = 0;
 2173             }
 2174         }
 2175 
 2176         // compress curr->buf to curr->len -- compress thread will drop curr
 2177         job->in = curr;
 2178 
 2179         // set job->more if there is more to compress after curr
 2180         more = next->len != 0;
 2181         job->more = more;
 2182 
 2183         // provide dictionary for this job, prepare dictionary for next job
 2184         job->out = dict;
 2185         if (more && g.setdict) {
 2186             if (curr->len >= DICT || job->out == NULL) {
 2187                 dict = curr;
 2188                 use_space(dict);
 2189             }
 2190             else {
 2191                 dict = get_space(&dict_pool);
 2192                 len = DICT - curr->len;
 2193                 memcpy(dict->buf, job->out->buf + (job->out->len - len), len);
 2194                 memcpy(dict->buf + len, curr->buf, curr->len);
 2195                 dict->len = DICT;
 2196             }
 2197         }
 2198 
 2199         // preparation of job is complete
 2200         job->seq = seq;
 2201         Trace(("-- read #%ld%s", seq, more ? "" : " (last)"));
 2202         if (++seq < 1)
 2203             throw(ERANGE, "overflow");
 2204 
 2205         // start another compress thread if needed
 2206         if (cthreads < seq && cthreads < g.procs) {
 2207             (void)launch(compress_thread, NULL);
 2208             cthreads++;
 2209         }
 2210 
 2211         // put job at end of compress list, let all the compressors know
 2212         possess(compress_have);
 2213         job->next = NULL;
 2214         *compress_tail = job;
 2215         compress_tail = &(job->next);
 2216         twist(compress_have, BY, +1);
 2217     } while (more);
 2218     drop_space(next);
 2219 
 2220     // wait for the write thread to complete (we leave the compress threads out
 2221     // there and waiting in case there is another stream to compress)
 2222     join(writeth);
 2223     writeth = NULL;
 2224     Trace(("-- write thread joined"));
 2225 }
 2226 
 2227 #endif
 2228 
 2229 // Repeated code in single_compress to compress available input and write it.
 2230 #define DEFLATE_WRITE(flush) \
 2231     do { \
 2232         do { \
 2233             strm->avail_out = out_size; \
 2234             strm->next_out = out; \
 2235             (void)deflate(strm, flush); \
 2236             clen += writen(g.outd, out, out_size - strm->avail_out); \
 2237         } while (strm->avail_out == 0); \
 2238         assert(strm->avail_in == 0); \
 2239     } while (0)
 2240 
 2241 // Do a simple compression in a single thread from ind to outd. If reset is
 2242 // true, instead free the memory that was allocated and retained for input,
 2243 // output, and deflate.
 2244 local void single_compress(int reset) {
 2245     size_t got;                     // amount of data in in[]
 2246     size_t more;                    // amount of data in next[] (0 if eof)
 2247     size_t start;                   // start of data in next[]
 2248     size_t have;                    // bytes in current block for -i
 2249     size_t hist;                    // offset of permitted history
 2250     int fresh;                      // if true, reset compression history
 2251     unsigned hash;                  // hash for rsyncable
 2252     unsigned char *scan;            // pointer for hash computation
 2253     size_t left;                    // bytes left to compress after hash hit
 2254     unsigned long head;             // header length
 2255     length_t ulen;                  // total uncompressed size
 2256     length_t clen;                  // total compressed size
 2257     unsigned long check;            // check value of uncompressed data
 2258     static unsigned out_size;       // size of output buffer
 2259     static unsigned char *in, *next, *out;  // reused i/o buffers
 2260     static z_stream *strm = NULL;   // reused deflate structure
 2261 
 2262     // if requested, just release the allocations and return
 2263     if (reset) {
 2264         if (strm != NULL) {
 2265             (void)deflateEnd(strm);
 2266             FREE(strm);
 2267             FREE(out);
 2268             FREE(next);
 2269             FREE(in);
 2270             strm = NULL;
 2271         }
 2272         return;
 2273     }
 2274 
 2275     // initialize the deflate structure if this is the first time
 2276     if (strm == NULL) {
 2277         int ret;                    // zlib return code
 2278 
 2279         out_size = g.block > MAXP2 ? MAXP2 : (unsigned)g.block;
 2280         in = alloc(NULL, g.block + DICT);
 2281         next = alloc(NULL, g.block + DICT);
 2282         out = alloc(NULL, out_size);
 2283         strm = alloc(NULL, sizeof(z_stream));
 2284         strm->zfree = ZFREE;
 2285         strm->zalloc = ZALLOC;
 2286         strm->opaque = OPAQUE;
 2287         ret = deflateInit2(strm, 6, Z_DEFLATED, -15, 8, g.strategy);
 2288         if (ret == Z_MEM_ERROR)
 2289             throw(ENOMEM, "not enough memory");
 2290         if (ret != Z_OK)
 2291             throw(EINVAL, "internal error");
 2292     }
 2293 
 2294     // write header
 2295     head = put_header();
 2296 
 2297     // set compression level in case it changed
 2298 #ifndef NOZOPFLI
 2299     if (g.level <= 9) {
 2300 #endif
 2301         (void)deflateReset(strm);
 2302         (void)deflateParams(strm, g.level, g.strategy);
 2303 #ifndef NOZOPFLI
 2304     }
 2305 #endif
 2306 
 2307     // do raw deflate and calculate check value
 2308     got = 0;
 2309     more = readn(g.ind, next, g.block);
 2310     ulen = more;
 2311     start = 0;
 2312     hist = 0;
 2313     clen = 0;
 2314     have = 0;
 2315     check = CHECK(0L, Z_NULL, 0);
 2316     hash = RSYNCHIT;
 2317     do {
 2318         // get data to compress, see if there is any more input
 2319         if (got == 0) {
 2320             scan = in;  in = next;  next = scan;
 2321             strm->next_in = in + start;
 2322             got = more;
 2323             if (g.level > 9) {
 2324                 left = start + more - hist;
 2325                 if (left > DICT)
 2326                     left = DICT;
 2327                 memcpy(next, in + ((start + more) - left), left);
 2328                 start = left;
 2329                 hist = 0;
 2330             }
 2331             else
 2332                 start = 0;
 2333             more = readn(g.ind, next + start, g.block);
 2334             ulen += more;
 2335         }
 2336 
 2337         // if rsyncable, compute hash until a hit or the end of the block
 2338         left = 0;
 2339         if (g.rsync && got) {
 2340             scan = strm->next_in;
 2341             left = got;
 2342             do {
 2343                 if (left == 0) {
 2344                     // went to the end -- if no more or no hit in size bytes,
 2345                     // then proceed to do a flush or finish with got bytes
 2346                     if (more == 0 || got == g.block)
 2347                         break;
 2348 
 2349                     // fill in[] with what's left there and as much as possible
 2350                     // from next[] -- set up to continue hash hit search
 2351                     if (g.level > 9) {
 2352                         left = (size_t)(strm->next_in - in) - hist;
 2353                         if (left > DICT)
 2354                             left = DICT;
 2355                     }
 2356                     memmove(in, strm->next_in - left, left + got);
 2357                     hist = 0;
 2358                     strm->next_in = in + left;
 2359                     scan = in + left + got;
 2360                     left = more > g.block - got ? g.block - got : more;
 2361                     memcpy(scan, next + start, left);
 2362                     got += left;
 2363                     more -= left;
 2364                     start += left;
 2365 
 2366                     // if that emptied the next buffer, try to refill it
 2367                     if (more == 0) {
 2368                         more = readn(g.ind, next, g.block);
 2369                         ulen += more;
 2370                         start = 0;
 2371                     }
 2372                 }
 2373                 left--;
 2374                 hash = ((hash << 1) ^ *scan++) & RSYNCMASK;
 2375             } while (hash != RSYNCHIT);
 2376             got -= left;
 2377         }
 2378 
 2379         // clear history for --independent option
 2380         fresh = 0;
 2381         if (!g.setdict) {
 2382             have += got;
 2383             if (have > g.block) {
 2384                 fresh = 1;
 2385                 have = got;
 2386             }
 2387         }
 2388 
 2389 #ifndef NOZOPFLI
 2390         if (g.level <= 9) {
 2391 #endif
 2392             // clear history if requested
 2393             if (fresh)
 2394                 (void)deflateReset(strm);
 2395 
 2396             // compress MAXP2-size chunks in case unsigned type is small
 2397             while (got > MAXP2) {
 2398                 strm->avail_in = MAXP2;
 2399                 check = CHECK(check, strm->next_in, strm->avail_in);
 2400                 DEFLATE_WRITE(Z_NO_FLUSH);
 2401                 got -= MAXP2;
 2402             }
 2403 
 2404             // compress the remainder, emit a block, finish if end of input
 2405             strm->avail_in = (unsigned)got;
 2406             got = left;
 2407             check = CHECK(check, strm->next_in, strm->avail_in);
 2408             if (more || got) {
 2409 #if ZLIB_VERNUM >= 0x1260
 2410                 if (zlib_vernum() >= 0x1260) {
 2411                     int bits;
 2412 
 2413                     DEFLATE_WRITE(Z_BLOCK);
 2414                     (void)deflatePending(strm, Z_NULL, &bits);
 2415                     if ((bits & 1) || !g.setdict)
 2416                         DEFLATE_WRITE(Z_SYNC_FLUSH);
 2417                     else if (bits & 7) {
 2418                         do {
 2419                             bits = deflatePrime(strm, 10, 2);
 2420                             assert(bits == Z_OK);
 2421                             (void)deflatePending(strm, Z_NULL, &bits);
 2422                         } while (bits & 7);
 2423                         DEFLATE_WRITE(Z_NO_FLUSH);
 2424                     }
 2425                 }
 2426                 else
 2427                     DEFLATE_WRITE(Z_SYNC_FLUSH);
 2428 #else
 2429                 DEFLATE_WRITE(Z_SYNC_FLUSH);
 2430 #endif
 2431                 if (!g.setdict)             // two markers when independent
 2432                     DEFLATE_WRITE(Z_FULL_FLUSH);
 2433             }
 2434             else
 2435                 DEFLATE_WRITE(Z_FINISH);
 2436 #ifndef NOZOPFLI
 2437         }
 2438         else {
 2439             // compress got bytes using zopfli, bring to byte boundary
 2440             unsigned char bits, *def;
 2441             size_t size, off;
 2442 
 2443             // discard history if requested
 2444             off = (size_t)(strm->next_in - in);
 2445             if (fresh)
 2446                 hist = off;
 2447 
 2448             def = NULL;
 2449             size = 0;
 2450             bits = 0;
 2451             ZopfliDeflatePart(&g.zopts, 2, !(more || left),
 2452                               in + hist, off - hist, (off - hist) + got,
 2453                               &bits, &def, &size);
 2454             bits &= 7;
 2455             if (more || left) {
 2456                 if ((bits & 1) || !g.setdict) {
 2457                     writen(g.outd, def, size);
 2458                     if (bits == 0 || bits > 5)
 2459                         writen(g.outd, (unsigned char *)"\0", 1);
 2460                     writen(g.outd, (unsigned char *)"\0\0\xff\xff", 4);
 2461                 }
 2462                 else {
 2463                     assert(size > 0);
 2464                     writen(g.outd, def, size - 1);
 2465                     if (bits)
 2466                         do {
 2467                             def[size - 1] += 2 << bits;
 2468                             writen(g.outd, def + size - 1, 1);
 2469                             def[size - 1] = 0;
 2470                             bits += 2;
 2471                         } while (bits < 8);
 2472                     writen(g.outd, def + size - 1, 1);
 2473                 }
 2474                 if (!g.setdict)             // two markers when independent
 2475                     writen(g.outd, (unsigned char *)"\0\0\0\xff\xff", 5);
 2476             }
 2477             else
 2478                 writen(g.outd, def, size);
 2479             free(def);
 2480             while (got > MAXP2) {
 2481                 check = CHECK(check, strm->next_in, MAXP2);
 2482                 strm->next_in += MAXP2;
 2483                 got -= MAXP2;
 2484             }
 2485             check = CHECK(check, strm->next_in, (unsigned)got);
 2486             strm->next_in += got;
 2487             got = left;
 2488         }
 2489 #endif
 2490 
 2491         // do until no more input
 2492     } while (more || got);
 2493 
 2494     // write trailer
 2495     put_trailer(ulen, clen, check, head);
 2496 }
 2497 
 2498 // --- decompression ---
 2499 
 2500 #ifndef NOTHREAD
 2501 // Parallel read thread. If the state is 1, then read a buffer and set the
 2502 // state to 0 when done, if the state is > 1, then end this thread.
 2503 local void load_read(void *dummy) {
 2504     size_t len;
 2505     ball_t err;                     // error information from throw()
 2506 
 2507     (void)dummy;
 2508 
 2509     Trace(("-- launched decompress read thread"));
 2510     try {
 2511         do {
 2512             possess(g.load_state);
 2513             wait_for(g.load_state, NOT_TO_BE, 0);
 2514             if (peek_lock(g.load_state) > 1) {
 2515                 release(g.load_state);
 2516                 break;
 2517             }
 2518             g.in_len = len = readn(g.ind, g.in_which ? g.in_buf : g.in_buf2,
 2519                                    BUF);
 2520             Trace(("-- decompress read thread read %lu bytes", len));
 2521             twist(g.load_state, TO, 0);
 2522         } while (len == BUF);
 2523     }
 2524     catch (err) {
 2525         THREADABORT(err);
 2526     }
 2527     Trace(("-- exited decompress read thread"));
 2528 }
 2529 
 2530 // Wait for load_read() to complete the current read operation. If the
 2531 // load_read() thread is not active, then return immediately.
 2532 local void load_wait(void) {
 2533     if (g.in_which == -1)
 2534         return;
 2535     possess(g.load_state);
 2536     wait_for(g.load_state, TO_BE, 0);
 2537     release(g.load_state);
 2538 }
 2539 #endif
 2540 
 2541 // load() is called when the input has been consumed in order to provide more
 2542 // input data: load the input buffer with BUF or fewer bytes (fewer if at end
 2543 // of file) from the file g.ind, set g.in_next to point to the g.in_left bytes
 2544 // read, update g.in_tot, and return g.in_left. g.in_eof is set to true when
 2545 // g.in_left has gone to zero and there is no more data left to read.
 2546 local size_t load(void) {
 2547     // if already detected end of file, do nothing
 2548     if (g.in_short) {
 2549         g.in_eof = 1;
 2550         g.in_left = 0;
 2551         return 0;
 2552     }
 2553 
 2554 #ifndef NOTHREAD
 2555     // if first time in or procs == 1, read a buffer to have something to
 2556     // return, otherwise wait for the previous read job to complete
 2557     if (g.procs > 1) {
 2558         // if first time, fire up the read thread, ask for a read
 2559         if (g.in_which == -1) {
 2560             g.in_which = 1;
 2561             g.load_state = new_lock(1);
 2562             g.load_thread = launch(load_read, NULL);
 2563         }
 2564 
 2565         // wait for the previously requested read to complete
 2566         load_wait();
 2567 
 2568         // set up input buffer with the data just read
 2569         g.in_next = g.in_which ? g.in_buf : g.in_buf2;
 2570         g.in_left = g.in_len;
 2571 
 2572         // if not at end of file, alert read thread to load next buffer,
 2573         // alternate between g.in_buf and g.in_buf2
 2574         if (g.in_len == BUF) {
 2575             g.in_which = 1 - g.in_which;
 2576             possess(g.load_state);
 2577             twist(g.load_state, TO, 1);
 2578         }
 2579 
 2580         // at end of file -- join read thread (already exited), clean up
 2581         else {
 2582             join(g.load_thread);
 2583             free_lock(g.load_state);
 2584             g.in_which = -1;
 2585         }
 2586     }
 2587     else
 2588 #endif
 2589     {
 2590         // don't use threads -- simply read a buffer into g.in_buf
 2591         g.in_left = readn(g.ind, g.in_next = g.in_buf, BUF);
 2592     }
 2593 
 2594     // note end of file
 2595     if (g.in_left < BUF) {
 2596         g.in_short = 1;
 2597 
 2598         // if we got bupkis, now is the time to mark eof
 2599         if (g.in_left == 0)
 2600             g.in_eof = 1;
 2601     }
 2602 
 2603     // update the total and return the available bytes
 2604     g.in_tot += g.in_left;
 2605     return g.in_left;
 2606 }
 2607 
 2608 // Terminate the load() operation. Empty buffer, mark end, close file (if not
 2609 // stdin), and free the name and comment obtained from the header, if present.
 2610 local void load_end(void) {
 2611 #ifndef NOTHREAD
 2612     // if the read thread is running, then end it
 2613     if (g.in_which != -1) {
 2614         // wait for the previously requested read to complete and send the
 2615         // thread a message to exit
 2616         possess(g.load_state);
 2617         wait_for(g.load_state, TO_BE, 0);
 2618         twist(g.load_state, TO, 2);
 2619 
 2620         // join the thread (which has exited or will very shortly) and clean up
 2621         join(g.load_thread);
 2622         free_lock(g.load_state);
 2623         g.in_which = -1;
 2624     }
 2625 #endif
 2626     g.in_left = 0;
 2627     g.in_short = 1;
 2628     g.in_eof = 1;
 2629     if (g.ind != 0)
 2630         close(g.ind);
 2631     RELEASE(g.hname);
 2632     RELEASE(g.hcomm);
 2633 }
 2634 
 2635 // Initialize for reading new input.
 2636 local void in_init(void) {
 2637     g.in_left = 0;
 2638     g.in_eof = 0;
 2639     g.in_short = 0;
 2640     g.in_tot = 0;
 2641 #ifndef NOTHREAD
 2642     g.in_which = -1;
 2643 #endif
 2644 }
 2645 
 2646 // Buffered reading macros for decompression and listing.
 2647 #define GET() (g.in_left == 0 && (g.in_eof || load() == 0) ? 0 : \
 2648                (g.in_left--, *g.in_next++))
 2649 #define GET2() (tmp2 = GET(), tmp2 + ((unsigned)(GET()) << 8))
 2650 #define GET4() (tmp4 = GET2(), tmp4 + ((unsigned long)(GET2()) << 16))
 2651 #define SKIP(dist) \
 2652     do { \
 2653         size_t togo = (dist); \
 2654         while (togo > g.in_left) { \
 2655             togo -= g.in_left; \
 2656             if (load() == 0) \
 2657                 return -3; \
 2658         } \
 2659         g.in_left -= togo; \
 2660         g.in_next += togo; \
 2661     } while (0)
 2662 
 2663 // GET(), GET2(), GET4() and SKIP() equivalents, with crc update.
 2664 #define GETC() (g.in_left == 0 && (g.in_eof || load() == 0) ? 0 : \
 2665                 (g.in_left--, crc = crc32z(crc, g.in_next, 1), *g.in_next++))
 2666 #define GET2C() (tmp2 = GETC(), tmp2 + ((unsigned)(GETC()) << 8))
 2667 #define GET4C() (tmp4 = GET2C(), tmp4 + ((unsigned long)(GET2C()) << 16))
 2668 #define SKIPC(dist) \
 2669     do { \
 2670         size_t togo = (dist); \
 2671         while (togo > g.in_left) { \
 2672             crc = crc32z(crc, g.in_next, g.in_left); \
 2673             togo -= g.in_left; \
 2674             if (load() == 0) \
 2675                 return -3; \
 2676         } \
 2677         crc = crc32z(crc, g.in_next, togo); \
 2678         g.in_left -= togo; \
 2679         g.in_next += togo; \
 2680     } while (0)
 2681 
 2682 // Get a zero-terminated string into allocated memory, with crc update.
 2683 #define GETZC(str) \
 2684     do { \
 2685         unsigned char *end; \
 2686         size_t copy, have, size = 0; \
 2687         have = 0; \
 2688         do { \
 2689             if (g.in_left == 0 && load() == 0) \
 2690                 return -3; \
 2691             end = memchr(g.in_next, 0, g.in_left); \
 2692             copy = end == NULL ? g.in_left : (size_t)(end - g.in_next) + 1; \
 2693             have = vmemcpy(&str, &size, have, g.in_next, copy); \
 2694             g.in_left -= copy; \
 2695             g.in_next += copy; \
 2696         } while (end == NULL); \
 2697         crc = crc32z(crc, (unsigned char *)str, have); \
 2698     } while (0)
 2699 
 2700 // Pull LSB order or MSB order integers from an unsigned char buffer.
 2701 #define PULL2L(p) ((p)[0] + ((unsigned)((p)[1]) << 8))
 2702 #define PULL4L(p) (PULL2L(p) + ((unsigned long)(PULL2L((p) + 2)) << 16))
 2703 #define PULL2M(p) (((unsigned)((p)[0]) << 8) + (p)[1])
 2704 #define PULL4M(p) (((unsigned long)(PULL2M(p)) << 16) + PULL2M((p) + 2))
 2705 
 2706 // Convert MS-DOS date and time to a Unix time, assuming current timezone.
 2707 // (You got a better idea?)
 2708 local time_t dos2time(unsigned long dos) {
 2709     struct tm tm;
 2710 
 2711     if (dos == 0)
 2712         return time(NULL);
 2713     tm.tm_year = ((int)(dos >> 25) & 0x7f) + 80;
 2714     tm.tm_mon  = ((int)(dos >> 21) & 0xf) - 1;
 2715     tm.tm_mday = (int)(dos >> 16) & 0x1f;
 2716     tm.tm_hour = (int)(dos >> 11) & 0x1f;
 2717     tm.tm_min  = (int)(dos >> 5) & 0x3f;
 2718     tm.tm_sec  = (int)(dos << 1) & 0x3e;
 2719     tm.tm_isdst = -1;           // figure out if DST or not
 2720     return mktime(&tm);
 2721 }
 2722 
 2723 // Convert an unsigned 32-bit integer to signed, even if long > 32 bits.
 2724 local long tolong(unsigned long val) {
 2725     return (long)(val & 0x7fffffffUL) - (long)(val & 0x80000000UL);
 2726 }
 2727 
 2728 // Process zip extra field to extract zip64 lengths and Unix mod time.
 2729 local int read_extra(unsigned len, int save) {
 2730     unsigned id, size, tmp2;
 2731     unsigned long tmp4;
 2732 
 2733     // process extra blocks
 2734     while (len >= 4) {
 2735         id = GET2();
 2736         size = GET2();
 2737         if (g.in_eof)
 2738             return -1;
 2739         len -= 4;
 2740         if (size > len)
 2741             break;
 2742         len -= size;
 2743         if (id == 0x0001) {
 2744             // Zip64 Extended Information Extra Field
 2745             g.zip64 = 1;
 2746             if (g.zip_ulen == LOW32 && size >= 8) {
 2747                 g.zip_ulen = GET4();
 2748                 SKIP(4);
 2749                 size -= 8;
 2750             }
 2751             if (g.zip_clen == LOW32 && size >= 8) {
 2752                 g.zip_clen = GET4();
 2753                 SKIP(4);
 2754                 size -= 8;
 2755             }
 2756         }
 2757         if (save) {
 2758             if ((id == 0x000d || id == 0x5855) && size >= 8) {
 2759                 // PKWare Unix or Info-ZIP Type 1 Unix block
 2760                 SKIP(4);
 2761                 g.stamp = tolong(GET4());
 2762                 size -= 8;
 2763             }
 2764             if (id == 0x5455 && size >= 5) {
 2765                 // Extended Timestamp block
 2766                 size--;
 2767                 if (GET() & 1) {
 2768                     g.stamp = tolong(GET4());
 2769                     size -= 4;
 2770                 }
 2771             }
 2772         }
 2773         SKIP(size);
 2774     }
 2775     SKIP(len);
 2776     return 0;
 2777 }
 2778 
 2779 // Read a gzip, zip, zlib, or Unix compress header from ind and return the
 2780 // compression method in the range 0..257. 8 is deflate, 256 is a zip method
 2781 // greater than 255, and 257 is LZW (compress). The only methods decompressed
 2782 // by pigz are 8 and 257. On error, return negative: -1 is immediate EOF, -2 is
 2783 // not a recognized compressed format (considering only the first two bytes of
 2784 // input), -3 is premature EOF within the header, -4 is unexpected header flag
 2785 // values, -5 is the zip central directory, and -6 is a failed gzip header crc
 2786 // check. If -2 is returned, the input pointer has been reset to the beginning.
 2787 // If the return value is not negative, then get_header() sets g.form to
 2788 // indicate gzip (0), zlib (1), or zip (2, or 3 if the entry is followed by a
 2789 // data descriptor), and the input points to the first byte of compressed data.
 2790 local int get_header(int save) {
 2791     unsigned magic;             // magic header
 2792     unsigned method;            // compression method
 2793     unsigned flags;             // header flags
 2794     unsigned fname, extra;      // name and extra field lengths
 2795     unsigned tmp2;              // for macro
 2796     unsigned long tmp4;         // for macro
 2797     unsigned long crc;          // gzip header crc
 2798 
 2799     // clear return information
 2800     if (save) {
 2801         g.stamp = 0;
 2802         RELEASE(g.hname);
 2803         RELEASE(g.hcomm);
 2804     }
 2805 
 2806     // see if it's a gzip, zlib, or lzw file
 2807     g.magic1 = GET();
 2808     if (g.in_eof) {
 2809         g.magic1 = -1;
 2810         return -1;
 2811     }
 2812     magic = (unsigned)g.magic1 << 8;
 2813     magic += GET();
 2814     if (g.in_eof)
 2815         return -2;
 2816     if (magic % 31 == 0 && (magic & 0x8f20) == 0x0800) {
 2817         // it's zlib
 2818         g.form = 1;
 2819         return 8;
 2820     }
 2821     if (magic == 0x1f9d) {          // it's lzw
 2822         g.form = -1;
 2823         return 257;
 2824     }
 2825     if (magic == 0x504b) {          // it's zip
 2826         magic = GET2();             // the rest of the signature
 2827         if (g.in_eof)
 2828             return -3;
 2829         if (magic == 0x0201 || magic == 0x0806)
 2830             return -5;              // central header or archive extra
 2831         if (magic != 0x0403)
 2832             return -4;              // not a local header
 2833         g.zip64 = 0;
 2834         SKIP(2);
 2835         flags = GET2();
 2836         if (flags & 0xf7f0)
 2837             return -4;
 2838         method = GET();             // return low byte of method or 256
 2839         if (GET() != 0 || flags & 1)
 2840             method = 256;           // unknown or encrypted
 2841         if (save)
 2842             g.stamp = dos2time(GET4());
 2843         else
 2844             SKIP(4);
 2845         g.zip_crc = GET4();
 2846         g.zip_clen = GET4();
 2847         g.zip_ulen = GET4();
 2848         fname = GET2();
 2849         extra = GET2();
 2850         if (save) {
 2851             char *next;
 2852 
 2853             if (g.in_eof)
 2854                 return -3;
 2855             next = g.hname = alloc(NULL, fname + 1);
 2856             while (fname > g.in_left) {
 2857                 memcpy(next, g.in_next, g.in_left);
 2858                 fname -= g.in_left;
 2859                 next += g.in_left;
 2860                 if (load() == 0)
 2861                     return -3;
 2862             }
 2863             memcpy(next, g.in_next, fname);
 2864             g.in_left -= fname;
 2865             g.in_next += fname;
 2866             next += fname;
 2867             *next = 0;
 2868         }
 2869         else
 2870             SKIP(fname);
 2871         read_extra(extra, save);
 2872         g.form = 2 + ((flags & 8) >> 3);
 2873         return g.in_eof ? -3 : (int)method;
 2874     }
 2875     if (magic != 0x1f8b) {          // not gzip
 2876         g.in_left++;                // return the second byte
 2877         g.in_next--;
 2878         return -2;
 2879     }
 2880 
 2881     // it's gzip -- get method and flags
 2882     crc = 0xf6e946c9;       // crc of 0x1f 0x8b
 2883     method = GETC();
 2884     flags = GETC();
 2885     if (flags & 0xe0)
 2886         return -4;
 2887 
 2888     // get time stamp
 2889     if (save)
 2890         g.stamp = tolong(GET4C());
 2891     else
 2892         SKIPC(4);
 2893 
 2894     // skip extra field and OS
 2895     SKIPC(2);
 2896 
 2897     // skip extra field, if present
 2898     if (flags & 4)
 2899         SKIPC(GET2C());
 2900 
 2901     // read file name, if present, into allocated memory
 2902     if (flags & 8) {
 2903         if (save)
 2904             GETZC(g.hname);
 2905         else
 2906             while (GETC() != 0)
 2907                 ;
 2908     }
 2909 
 2910     // read comment, if present, into allocated memory
 2911     if (flags & 16) {
 2912         if (save)
 2913             GETZC(g.hcomm);
 2914         else
 2915             while (GETC() != 0)
 2916                 ;
 2917     }
 2918 
 2919     // check header crc
 2920     if ((flags & 2) && GET2() != (crc & 0xffff))
 2921         return -6;
 2922 
 2923     // return gzip compression method
 2924     g.form = 0;
 2925     return g.in_eof ? -3 : (int)method;
 2926 }
 2927 
 2928 // Process the remainder of a zip file after the first entry. Return true if
 2929 // the next signature is another local file header. If listing verbosely, then
 2930 // search the remainder of the zip file for the central file header
 2931 // corresponding to the first zip entry, and save the file comment, if any.
 2932 local int more_zip_entries(void) {
 2933     unsigned long sig;
 2934     int ret, n;
 2935     unsigned char *first;
 2936     unsigned tmp2;              // for macro
 2937     unsigned long tmp4;         // for macro
 2938     unsigned char const central[] = {0x50, 0x4b, 1, 2};
 2939 
 2940     sig = GET4();
 2941     ret = !g.in_eof && sig == 0x04034b50;   // true if another entry follows
 2942     if (!g.list || g.verbosity < 2)
 2943         return ret;
 2944 
 2945     // if it was a central file header signature, then already four bytes
 2946     // into a central directory header -- otherwise search for the next one
 2947     n = sig == 0x02014b50 ? 4 : 0;  // number of bytes into central header
 2948     for (;;) {
 2949         // assure that more input is available
 2950         if (g.in_left == 0 && load() == 0)      // never found it!
 2951             return ret;
 2952         if (n == 0) {
 2953             // look for first byte in central signature
 2954             first = memchr(g.in_next, central[0], g.in_left);
 2955             if (first == NULL) {
 2956                 // not found -- go get the next buffer and keep looking
 2957                 g.in_left = 0;
 2958             }
 2959             else {
 2960                 // found -- continue search at next byte
 2961                 n++;
 2962                 g.in_left -= first - g.in_next + 1;
 2963                 g.in_next = first + 1;
 2964             }
 2965         }
 2966         else if (n < 4) {
 2967             // look for the remaining bytes in the central signature
 2968             if (g.in_next[0] == central[n]) {
 2969                 n++;
 2970                 g.in_next++;
 2971                 g.in_left--;
 2972             }
 2973             else
 2974                 n = 0;      // mismatch -- restart search with this byte
 2975         }
 2976         else {
 2977             // Now in a suspected central file header, just past the signature.
 2978             // Read the rest of the fixed-length portion of the header.
 2979             unsigned char head[CEN];
 2980             size_t need = CEN, part = 0, len, i;
 2981 
 2982             if (need > g.in_left) {     // will only need to do this once
 2983                 part = g.in_left;
 2984                 memcpy(head + CEN - need, g.in_next, part);
 2985                 need -= part;
 2986                 g.in_left = 0;
 2987                 if (load() == 0)                // never found it!
 2988                     return ret;
 2989             }
 2990             memcpy(head + CEN - need, g.in_next, need);
 2991 
 2992             // Determine to sufficient probability that this is the droid we're
 2993             // looking for, by checking the CRC and the local header offset.
 2994             if (PULL4L(head + 12) == g.out_check && PULL4L(head + 38) == 0) {
 2995                 // Update the number of bytes consumed from the current buffer.
 2996                 g.in_next += need;
 2997                 g.in_left -= need;
 2998 
 2999                 // Get the comment length.
 3000                 len = PULL2L(head + 28);
 3001                 if (len == 0)                   // no comment
 3002                     return ret;
 3003 
 3004                 // Skip the file name and extra field.
 3005                 SKIP(PULL2L(head + 24) + (unsigned long)PULL2L(head + 26));
 3006 
 3007                 // Save the comment field.
 3008                 need = len;
 3009                 g.hcomm = alloc(NULL, len + 1);
 3010                 while (need > g.in_left) {
 3011                     memcpy(g.hcomm + len - need, g.in_next, g.in_left);
 3012                     need -= g.in_left;
 3013                     g.in_left = 0;
 3014                     if (load() == 0) {          // premature EOF
 3015                         RELEASE(g.hcomm);
 3016                         return ret;
 3017                     }
 3018                 }
 3019                 memcpy(g.hcomm + len - need, g.in_next, need);
 3020                 g.in_next += need;
 3021                 g.in_left -= need;
 3022                 for (i = 0; i < len; i++)
 3023                     if (g.hcomm[i] == 0)
 3024                         g.hcomm[i] = ' ';
 3025                 g.hcomm[len] = 0;
 3026                 return ret;
 3027             }
 3028             else {
 3029                 // Nope, false alarm. Restart the search at the first byte
 3030                 // after what we thought was the central file header signature.
 3031                 if (part) {
 3032                     // Move buffer data up and insert the part of the header
 3033                     // data read from the previous buffer.
 3034                     memmove(g.in_next + part, g.in_next, g.in_left);
 3035                     memcpy(g.in_next, head, part);
 3036                     g.in_left += part;
 3037                 }
 3038                 n = 0;
 3039             }
 3040         }
 3041     }
 3042 }
 3043 
 3044 // --- list contents of compressed input (gzip, zlib, or lzw) ---
 3045 
 3046 // Find standard compressed file suffix, return length of suffix.
 3047 local size_t compressed_suffix(char *nm) {
 3048     size_t len;
 3049 
 3050     len = strlen(nm);
 3051     if (len > 4) {
 3052         nm += len - 4;
 3053         len = 4;
 3054         if (strcmp(nm, ".zip") == 0 || strcmp(nm, ".ZIP") == 0 ||
 3055             strcmp(nm, ".tgz") == 0)
 3056             return 4;
 3057     }
 3058     if (len > 3) {
 3059         nm += len - 3;
 3060         len = 3;
 3061         if (strcmp(nm, ".gz") == 0 || strcmp(nm, "-gz") == 0 ||
 3062             strcmp(nm, ".zz") == 0 || strcmp(nm, "-zz") == 0)
 3063             return 3;
 3064     }
 3065     if (len > 2) {
 3066         nm += len - 2;
 3067         if (strcmp(nm, ".z") == 0 || strcmp(nm, "-z") == 0 ||
 3068             strcmp(nm, "_z") == 0 || strcmp(nm, ".Z") == 0)
 3069             return 2;
 3070     }
 3071     return 0;
 3072 }
 3073 
 3074 // Listing file name lengths for -l and -lv.
 3075 #define NAMEMAX1 48     // name display limit at verbosity 1
 3076 #define NAMEMAX2 16     // name display limit at verbosity 2
 3077 
 3078 // Print gzip, lzw, zlib, or zip file information.
 3079 local void show_info(int method, unsigned long check, length_t len, int cont) {
 3080     size_t max;             // maximum name length for current verbosity
 3081     size_t n;               // name length without suffix
 3082     time_t now;             // for getting current year
 3083     char mod[26];           // modification time in text
 3084     char tag[NAMEMAX1+1];   // header or file name, possibly truncated
 3085 
 3086     // create abbreviated name from header file name or actual file name
 3087     max = g.verbosity > 1 ? NAMEMAX2 : NAMEMAX1;
 3088     memset(tag, 0, max + 1);
 3089     if (cont)
 3090         strncpy(tag, "<...>", max + 1);
 3091     else if (g.hname == NULL) {
 3092         n = strlen(g.inf) - compressed_suffix(g.inf);
 3093         memcpy(tag, g.inf, n > max + 1 ? max + 1 : n);
 3094         if (strcmp(g.inf + n, ".tgz") == 0 && n < max + 1)
 3095             strncpy(tag + n, ".tar", max + 1 - n);
 3096     }
 3097     else
 3098         strncpy(tag, g.hname, max + 1);
 3099     if (tag[max])
 3100         strcpy(tag + max - 3, "...");
 3101 
 3102     // convert time stamp to text
 3103     if (g.stamp) {
 3104         strcpy(mod, ctime(&g.stamp));
 3105         now = time(NULL);
 3106         if (strcmp(mod + 20, ctime(&now) + 20) != 0)
 3107             strcpy(mod + 11, mod + 19);
 3108     }
 3109     else
 3110         strcpy(mod + 4, "------ -----");
 3111     mod[16] = 0;
 3112 
 3113     // if first time, print header
 3114     if (g.first) {
 3115         if (g.verbosity > 1)
 3116             fputs("method    check    timestamp    ", stdout);
 3117         if (g.verbosity > 0)
 3118             puts("compressed   original reduced  name");
 3119         g.first = 0;
 3120     }
 3121 
 3122     // print information
 3123     if (g.verbosity > 1) {
 3124         if (g.form == 3 && !g.decode)
 3125             printf("zip%3d  --------  %s  ", method, mod + 4);
 3126         else if (g.form > 1)
 3127             printf("zip%3d  %08lx  %s  ", method, check, mod + 4);
 3128         else if (g.form == 1)
 3129             printf("zlib%2d  %08lx  %s  ", method, check, mod + 4);
 3130         else if (method == 257)
 3131             printf("lzw     --------  %s  ", mod + 4);
 3132         else
 3133             printf("gzip%2d  %08lx  %s  ", method, check, mod + 4);
 3134     }
 3135     if (g.verbosity > 0) {
 3136         // compute reduction percent -- allow divide-by-zero, displays as -inf%
 3137         double red = 100. * (len - (double)g.in_tot) / len;
 3138         if ((g.form == 3 && !g.decode) ||
 3139             (method == 8 && g.in_tot > (len + (len >> 10) + 12)) ||
 3140             (method == 257 && g.in_tot > len + (len >> 1) + 3))
 3141 #if __STDC_VERSION__-0 >= 199901L || __GNUC__-0 >= 3
 3142             printf("%10jd %10jd?  unk    %s\n",
 3143                    (intmax_t)g.in_tot, (intmax_t)len, tag);
 3144         else
 3145             printf("%10jd %10jd %6.1f%%  %s\n",
 3146                    (intmax_t)g.in_tot, (intmax_t)len, red, tag);
 3147 #else
 3148             printf(sizeof(off_t) == sizeof(long) ?
 3149                    "%10ld %10ld?  unk    %s\n" : "%10lld %10lld?  unk    %s\n",
 3150                    g.in_tot, len, tag);
 3151         else
 3152             printf(sizeof(off_t) == sizeof(long) ?
 3153                    "%10ld %10ld %6.1f%%  %s\n" : "%10lld %10lld %6.1f%%  %s\n",
 3154                    g.in_tot, len, red, tag);
 3155 #endif
 3156     }
 3157     if (g.verbosity > 1 && g.hcomm != NULL)
 3158         puts(g.hcomm);
 3159 }
 3160 
 3161 // List content information about the gzip file at ind (only works if the gzip
 3162 // file contains a single gzip stream with no junk at the end, and only works
 3163 // well if the uncompressed length is less than 4 GB).
 3164 local void list_info(void) {
 3165     int method;             // get_header() return value
 3166     size_t n;               // available trailer bytes
 3167     off_t at;               // used to calculate compressed length
 3168     unsigned char tail[8];  // trailer containing check and length
 3169     unsigned long check;    // check value
 3170     length_t len;           // length from trailer
 3171 
 3172     // initialize input buffer
 3173     in_init();
 3174 
 3175     // read header information and position input after header
 3176     method = get_header(1);
 3177     if (method < 0) {
 3178         complain(method == -6 ? "skipping: %s corrupt: header crc error" :
 3179                  method == -1 ? "skipping: %s empty" :
 3180                  "skipping: %s unrecognized format", g.inf);
 3181         return;
 3182     }
 3183 
 3184 #ifndef NOTHREAD
 3185     // wait for read thread to complete current read() operation, to permit
 3186     // seeking and reading on g.ind here in the main thread
 3187     load_wait();
 3188 #endif
 3189 
 3190     // list zip file
 3191     if (g.form > 1) {
 3192         more_zip_entries();         // get first entry comment, if any
 3193         g.in_tot = g.zip_clen;
 3194         show_info(method, g.zip_crc, g.zip_ulen, 0);
 3195         return;
 3196     }
 3197 
 3198     // list zlib file
 3199     if (g.form == 1) {
 3200         at = lseek(g.ind, 0, SEEK_END);
 3201         if (at == -1) {
 3202             check = 0;
 3203             do {
 3204                 len = g.in_left < 4 ? g.in_left : 4;
 3205                 g.in_next += g.in_left - len;
 3206                 while (len--)
 3207                     check = (check << 8) + *g.in_next++;
 3208             } while (load() != 0);
 3209             check &= LOW32;
 3210         }
 3211         else {
 3212             g.in_tot = (length_t)at;
 3213             lseek(g.ind, -4, SEEK_END);
 3214             readn(g.ind, tail, 4);
 3215             check = PULL4M(tail);
 3216         }
 3217         g.in_tot -= 6;
 3218         show_info(method, check, 0, 0);
 3219         return;
 3220     }
 3221 
 3222     // list lzw file
 3223     if (method == 257) {
 3224         at = lseek(g.ind, 0, SEEK_END);
 3225         if (at == -1)
 3226             while (load() != 0)
 3227                 ;
 3228         else
 3229             g.in_tot = (length_t)at;
 3230         g.in_tot -= 3;
 3231         show_info(method, 0, 0, 0);
 3232         return;
 3233     }
 3234 
 3235     // skip to end to get trailer (8 bytes), compute compressed length
 3236     if (g.in_short) {                   // whole thing already read
 3237         if (g.in_left < 8) {
 3238             complain("skipping: %s not a valid gzip file", g.inf);
 3239             return;
 3240         }
 3241         g.in_tot = g.in_left - 8;       // compressed size
 3242         memcpy(tail, g.in_next + (g.in_left - 8), 8);
 3243     }
 3244     else if ((at = lseek(g.ind, -8, SEEK_END)) != -1) {
 3245         g.in_tot = (length_t)at - g.in_tot + g.in_left; // compressed size
 3246         readn(g.ind, tail, 8);          // get trailer
 3247     }
 3248     else {                              // can't seek
 3249         len = g.in_tot - g.in_left;     // save header size
 3250         do {
 3251             n = g.in_left < 8 ? g.in_left : 8;
 3252             memcpy(tail, g.in_next + (g.in_left - n), n);
 3253             load();
 3254         } while (g.in_left == BUF);     // read until end
 3255         if (g.in_left < 8) {
 3256             if (n + g.in_left < 8) {
 3257                 complain("skipping: %s not a valid gzip file", g.inf);
 3258                 return;
 3259             }
 3260             if (g.in_left) {
 3261                 if (n + g.in_left > 8)
 3262                     memcpy(tail, tail + n - (8 - g.in_left), 8 - g.in_left);
 3263                 memcpy(tail + 8 - g.in_left, g.in_next, g.in_left);
 3264             }
 3265         }
 3266         else
 3267             memcpy(tail, g.in_next + (g.in_left - 8), 8);
 3268         g.in_tot -= len + 8;
 3269     }
 3270     if (g.in_tot < 2) {
 3271         complain("skipping: %s not a valid gzip file", g.inf);
 3272         return;
 3273     }
 3274 
 3275     // convert trailer to check and uncompressed length (modulo 2^32)
 3276     check = PULL4L(tail);
 3277     len = PULL4L(tail + 4);
 3278 
 3279     // list information about contents
 3280     show_info(method, check, len, 0);
 3281 }
 3282 
 3283 // --- copy input to output (when acting like cat) ---
 3284 
 3285 local void cat(void) {
 3286     // copy the first header byte read, if any
 3287     if (g.magic1 != -1) {
 3288         unsigned char buf[1] = {g.magic1};
 3289         g.out_tot += writen(g.outd, buf, 1);
 3290     }
 3291 
 3292     // copy the remainder of the input to the output
 3293     while (g.in_left) {
 3294         g.out_tot += writen(g.outd, g.in_next, g.in_left);
 3295         g.in_left = 0;
 3296         load();
 3297     }
 3298 }
 3299 
 3300 // --- decompress deflate input ---
 3301 
 3302 // Call-back input function for inflateBack().
 3303 local unsigned inb(void *desc, unsigned char **buf) {
 3304     (void)desc;
 3305     if (g.in_left == 0)
 3306         load();
 3307     *buf = g.in_next;
 3308     unsigned len = g.in_left > UINT_MAX ? UINT_MAX : (unsigned)g.in_left;
 3309     g.in_next += len;
 3310     g.in_left -= len;
 3311     return len;
 3312 }
 3313 
 3314 // Output buffers and window for infchk() and unlzw().
 3315 #define OUTSIZE 32768U      // must be at least 32K for inflateBack() window
 3316 local unsigned char out_buf[OUTSIZE];
 3317 
 3318 #ifndef NOTHREAD
 3319 // Output data for parallel write and check.
 3320 local unsigned char out_copy[OUTSIZE];
 3321 local size_t out_len;
 3322 
 3323 // outb threads states.
 3324 local lock *outb_write_more = NULL;
 3325 local lock *outb_check_more;
 3326 
 3327 // Output write thread.
 3328 local void outb_write(void *dummy) {
 3329     size_t len;
 3330     ball_t err;                     // error information from throw()
 3331 
 3332     (void)dummy;
 3333 
 3334     Trace(("-- launched decompress write thread"));
 3335     try {
 3336         do {
 3337             possess(outb_write_more);
 3338             wait_for(outb_write_more, TO_BE, 1);
 3339             len = out_len;
 3340             if (len && g.decode == 1)
 3341                 writen(g.outd, out_copy, len);
 3342             Trace(("-- decompress wrote %lu bytes", len));
 3343             twist(outb_write_more, TO, 0);
 3344         } while (len);
 3345     }
 3346     catch (err) {
 3347         THREADABORT(err);
 3348     }
 3349     Trace(("-- exited decompress write thread"));
 3350 }
 3351 
 3352 // Output check thread.
 3353 local void outb_check(void *dummy) {
 3354     size_t len;
 3355     ball_t err;                     // error information from throw()
 3356 
 3357     (void)dummy;
 3358 
 3359     Trace(("-- launched decompress check thread"));
 3360     try {
 3361         do {
 3362             possess(outb_check_more);
 3363             wait_for(outb_check_more, TO_BE, 1);
 3364             len = out_len;
 3365             g.out_check = CHECK(g.out_check, out_copy, len);
 3366             Trace(("-- decompress checked %lu bytes", len));
 3367             twist(outb_check_more, TO, 0);
 3368         } while (len);
 3369     }
 3370     catch (err) {
 3371         THREADABORT(err);
 3372     }
 3373     Trace(("-- exited decompress check thread"));
 3374 }
 3375 #endif
 3376 
 3377 // Call-back output function for inflateBack(). Wait for the last write and
 3378 // check calculation to complete, copy the write buffer, and then alert the
 3379 // write and check threads and return for more decompression while that's going
 3380 // on (or just write and check if no threads or if proc == 1).
 3381 local int outb(void *desc, unsigned char *buf, unsigned len) {
 3382     (void)desc;
 3383 
 3384 #ifndef NOTHREAD
 3385     static thread *wr, *ch;
 3386 
 3387     if (g.procs > 1) {
 3388         // if first time, initialize state and launch threads
 3389         if (outb_write_more == NULL) {
 3390             outb_write_more = new_lock(0);
 3391             outb_check_more = new_lock(0);
 3392             wr = launch(outb_write, NULL);
 3393             ch = launch(outb_check, NULL);
 3394         }
 3395 
 3396         // wait for previous write and check threads to complete
 3397         possess(outb_check_more);
 3398         wait_for(outb_check_more, TO_BE, 0);
 3399         possess(outb_write_more);
 3400         wait_for(outb_write_more, TO_BE, 0);
 3401 
 3402         // copy the output and alert the worker bees
 3403         out_len = len;
 3404         g.out_tot += len;
 3405         memcpy(out_copy, buf, len);
 3406         twist(outb_write_more, TO, 1);
 3407         twist(outb_check_more, TO, 1);
 3408 
 3409         // if requested with len == 0, clean up -- terminate and join write and
 3410         // check threads, free lock
 3411         if (len == 0 && outb_write_more != NULL) {
 3412             join(ch);
 3413             join(wr);
 3414             free_lock(outb_check_more);
 3415             free_lock(outb_write_more);
 3416             outb_write_more = NULL;
 3417         }
 3418 
 3419         // return for more decompression while last buffer is being written and
 3420         // having its check value calculated -- we wait for those to finish the
 3421         // next time this function is called
 3422         return 0;
 3423     }
 3424 #endif
 3425 
 3426     // if just one process or no threads, then do it without threads
 3427     if (len) {
 3428         if (g.decode == 1)
 3429             writen(g.outd, buf, len);
 3430         g.out_check = CHECK(g.out_check, buf, len);
 3431         g.out_tot += len;
 3432     }
 3433     return 0;
 3434 }
 3435 
 3436 // Zip file data descriptor signature. This signature may or may not precede
 3437 // the CRC and lengths, with either resulting in a valid zip file! There is
 3438 // some odd code below that tries to detect and accommodate both cases.
 3439 #define SIG 0x08074b50
 3440 
 3441 // Inflate for decompression or testing. Decompress from ind to outd unless
 3442 // decode != 1, in which case just test ind, and then also list if list != 0;
 3443 // look for and decode multiple, concatenated gzip and/or zlib streams; read
 3444 // and check the gzip, zlib, or zip trailer.
 3445 local void infchk(void) {
 3446     int ret, cont, more;
 3447     unsigned long check, len;
 3448     z_stream strm;
 3449     unsigned tmp2;
 3450     unsigned long tmp4;
 3451     length_t clen;
 3452 
 3453     cont = more = 0;
 3454     do {
 3455         // header already read -- set up for decompression
 3456         g.in_tot = g.in_left;       // track compressed data length
 3457         g.out_tot = 0;
 3458         g.out_check = CHECK(0L, Z_NULL, 0);
 3459         strm.zalloc = ZALLOC;
 3460         strm.zfree = ZFREE;
 3461         strm.opaque = OPAQUE;
 3462         ret = inflateBackInit(&strm, 15, out_buf);
 3463         if (ret == Z_MEM_ERROR)
 3464             throw(ENOMEM, "not enough memory");
 3465         if (ret != Z_OK)
 3466             throw(EINVAL, "internal error");
 3467 
 3468         // decompress, compute lengths and check value
 3469         strm.avail_in = 0;
 3470         strm.next_in = Z_NULL;
 3471         ret = inflateBack(&strm, inb, NULL, outb, NULL);
 3472         inflateBackEnd(&strm);
 3473         if (ret == Z_DATA_ERROR)
 3474             throw(EDOM, "%s: corrupted -- invalid deflate data (%s)",
 3475                   g.inf, strm.msg);
 3476         if (ret == Z_BUF_ERROR)
 3477             throw(EDOM, "%s: corrupted -- incomplete deflate data", g.inf);
 3478         if (ret != Z_STREAM_END)
 3479             throw(EINVAL, "internal error");
 3480         g.in_left += strm.avail_in;
 3481         g.in_next = strm.next_in;
 3482         outb(NULL, NULL, 0);        // finish off final write and check
 3483 
 3484         // compute compressed data length
 3485         clen = g.in_tot - g.in_left;
 3486 
 3487         // read and check trailer
 3488         if (g.form > 1) {           // zip local trailer (if any)
 3489             if (g.form == 3) {      // data descriptor follows
 3490                 // get data descriptor values, assuming no signature
 3491                 g.zip_crc = GET4();
 3492                 g.zip_clen = GET4();
 3493                 g.zip_ulen = GET4();        // ZIP64 -> high clen, not ulen
 3494 
 3495                 // deduce whether or not a signature precedes the values
 3496                 if (g.zip_crc == SIG &&         // might be the signature
 3497                     // if the expected CRC is not SIG, then it's a signature
 3498                     (g.out_check != SIG ||      // assume signature
 3499                      // now we're in a very rare case where CRC == SIG -- the
 3500                      // first four bytes could be the signature or the CRC
 3501                      (g.zip_clen == SIG &&      // if not, then no signature
 3502                       // now we have the first two words are SIG and the
 3503                       // expected CRC is SIG, so it could be a signature and
 3504                       // the CRC, or it could be the CRC and a compressed
 3505                       // length that is *also* SIG (!) -- so check the low 32
 3506                       // bits of the expected compressed length for SIG
 3507                       ((clen & LOW32) != SIG || // assume signature and CRC
 3508                        // now the expected CRC *and* the expected low 32 bits
 3509                        // of the compressed length are SIG -- this is so
 3510                        // incredibly unlikely, clearly someone is messing with
 3511                        // us, but we continue ... if the next four bytes are
 3512                        // not SIG, then there is not a signature -- check those
 3513                        // bytes, currently in g.zip_ulen:
 3514                        (g.zip_ulen == SIG &&    // if not, then no signature
 3515                         // we have three SIGs in a row in the descriptor, and
 3516                         // both the expected CRC and the expected clen are SIG
 3517                         // -- the first one is a signature if we don't expect
 3518                         // the third word to be SIG, which is either the low 32
 3519                         // bits of ulen, or if ZIP64, the high 32 bits of clen:
 3520                         (g.zip64 ? clen >> 32 : g.out_tot) != SIG
 3521                         // if that last compare was equal, then the expected
 3522                         // values for the CRC, the low 32 bits of clen, *and*
 3523                         // the low 32 bits of ulen are all SIG (!!), or in the
 3524                         // case of ZIP64, even crazier, the CRC and *both*
 3525                         // 32-bit halves of clen are all SIG (clen > 500
 3526                         // petabytes!!!) ... we can no longer discriminate the
 3527                         // hypotheses, so we will assume no signature
 3528                         ))))) {
 3529                     // first four bytes were actually the descriptor -- shift
 3530                     // the values down and get another four bytes
 3531                     g.zip_crc = g.zip_clen;
 3532                     g.zip_clen = g.zip_ulen;
 3533                     g.zip_ulen = GET4();
 3534                 }
 3535 
 3536                 // if ZIP64, then ulen is really the high word of clen -- get
 3537                 // the actual ulen and skip its high word as well (we only
 3538                 // compare the low 32 bits of the lengths to verify)
 3539                 if (g.zip64) {
 3540                     g.zip_ulen = GET4();
 3541                     (void)GET4();
 3542                 }
 3543                 if (g.in_eof)
 3544                     throw(EDOM, "%s: corrupted entry -- missing trailer",
 3545                           g.inf);
 3546             }
 3547             check = g.zip_crc;
 3548             if (check != g.out_check)
 3549                 throw(EDOM, "%s: corrupted entry -- crc32 mismatch", g.inf);
 3550             if (g.zip_clen != (clen & LOW32) ||
 3551                 g.zip_ulen != (g.out_tot & LOW32))
 3552                 throw(EDOM, "%s: corrupted entry -- length mismatch",
 3553                       g.inf);
 3554             more = more_zip_entries();  // see if more entries, get comment
 3555         }
 3556         else if (g.form == 1) {     // zlib (big-endian) trailer
 3557             check = (unsigned long)(GET()) << 24;
 3558             check += (unsigned long)(GET()) << 16;
 3559             check += (unsigned)(GET()) << 8;
 3560             check += GET();
 3561             if (g.in_eof)
 3562                 throw(EDOM, "%s: corrupted -- missing trailer", g.inf);
 3563             if (check != g.out_check)
 3564                 throw(EDOM, "%s: corrupted -- adler32 mismatch", g.inf);
 3565         }
 3566         else {                      // gzip trailer
 3567             check = GET4();
 3568             len = GET4();
 3569             if (g.in_eof)
 3570                 throw(EDOM, "%s: corrupted -- missing trailer", g.inf);
 3571             if (check != g.out_check)
 3572                 throw(EDOM, "%s: corrupted -- crc32 mismatch", g.inf);
 3573             if (len != (g.out_tot & LOW32))
 3574                 throw(EDOM, "%s: corrupted -- length mismatch", g.inf);
 3575         }
 3576 
 3577         // show file information if requested
 3578         if (g.list) {
 3579             g.in_tot = clen;
 3580             show_info(8, check, g.out_tot, cont);
 3581             cont = 1;
 3582         }
 3583 
 3584         // if a gzip entry follows a gzip entry, decompress it (don't replace
 3585         // saved header information from first entry)
 3586     } while (g.form == 0 && (ret = get_header(0)) == 8);
 3587 
 3588     // gzip -cdf copies junk after gzip stream directly to output
 3589     if (g.form == 0 && ret == -2 && g.force && g.pipeout && g.decode != 2 &&
 3590         !g.list)
 3591         cat();
 3592 
 3593     // check for more entries in zip file
 3594     else if (more) {
 3595         complain("warning: %s: entries after the first were ignored", g.inf);
 3596         g.keep = 1;         // don't delete the .zip file
 3597     }
 3598 
 3599     // check for non-gzip after gzip stream, or anything after zlib stream
 3600     else if ((g.verbosity > 1 && g.form == 0 && ret != -1) ||
 3601              (g.form == 1 && (GET(), !g.in_eof)))
 3602         complain("warning: %s: trailing junk was ignored", g.inf);
 3603 }
 3604 
 3605 // --- decompress Unix compress (LZW) input ---
 3606 
 3607 // Type for accumulating bits. 23 bits will be used to accumulate up to 16-bit
 3608 // symbols.
 3609 typedef unsigned long bits_t;
 3610 
 3611 #define NOMORE() (g.in_left == 0 && (g.in_eof || load() == 0))
 3612 #define NEXT() (g.in_left--, (unsigned)*g.in_next++)
 3613 
 3614 // Decompress a compress (LZW) file from ind to outd. The compress magic header
 3615 // (two bytes) has already been read and verified.
 3616 local void unlzw(void) {
 3617     unsigned bits;              // current bits per code (9..16)
 3618     unsigned mask;              // mask for current bits codes = (1<<bits)-1
 3619     bits_t buf;                 // bit buffer (need 23 bits)
 3620     unsigned left;              // bits left in buf (0..7 after code pulled)
 3621     length_t mark;              // offset where last change in bits began
 3622     unsigned code;              // code, table traversal index
 3623     unsigned max;               // maximum bits per code for this stream
 3624     unsigned flags;             // compress flags, then block compress flag
 3625     unsigned end;               // last valid entry in prefix/suffix tables
 3626     unsigned prev;              // previous code
 3627     unsigned final;             // last character written for previous code
 3628     unsigned stack;             // next position for reversed string
 3629     unsigned outcnt;            // bytes in output buffer
 3630     // memory for unlzw() -- the first 256 entries of prefix[] and suffix[] are
 3631     // never used, so could have offset the index but it's faster to waste a
 3632     // little memory
 3633     uint_least16_t prefix[65536];       // index to LZW prefix string
 3634     unsigned char suffix[65536];        // one-character LZW suffix
 3635     unsigned char match[65280 + 2];     // buffer for reversed match
 3636 
 3637     // process remainder of compress header -- a flags byte
 3638     g.out_tot = 0;
 3639     if (NOMORE())
 3640         throw(EDOM, "%s: lzw premature end", g.inf);
 3641     flags = NEXT();
 3642     if (flags & 0x60)
 3643         throw(EDOM, "%s: unknown lzw flags set", g.inf);
 3644     max = flags & 0x1f;
 3645     if (max < 9 || max > 16)
 3646         throw(EDOM, "%s: lzw bits out of range", g.inf);
 3647     if (max == 9)                           // 9 doesn't really mean 9
 3648         max = 10;
 3649     flags &= 0x80;                          // true if block compress
 3650 
 3651     // mark the start of the compressed data for computing the first flush
 3652     mark = g.in_tot - g.in_left;
 3653 
 3654     // clear table, start at nine bits per symbol
 3655     bits = 9;
 3656     mask = 0x1ff;
 3657     end = flags ? 256 : 255;
 3658 
 3659     // set up: get first 9-bit code, which is the first decompressed byte, but
 3660     // don't create a table entry until the next code
 3661     if (NOMORE())                           // no compressed data is ok
 3662         return;
 3663     buf = NEXT();
 3664     if (NOMORE())
 3665         throw(EDOM, "%s: lzw premature end", g.inf);  // need nine bits
 3666     buf += NEXT() << 8;
 3667     final = prev = buf & mask;              // code
 3668     buf >>= bits;
 3669     left = 16 - bits;
 3670     if (prev > 255)
 3671         throw(EDOM, "%s: invalid lzw code", g.inf);
 3672     out_buf[0] = (unsigned char)final;      // write first decompressed byte
 3673     outcnt = 1;
 3674 
 3675     // decode codes
 3676     stack = 0;
 3677     for (;;) {
 3678         // if the table will be full after this, increment the code size
 3679         if (end >= mask && bits < max) {
 3680             // flush unused input bits and bytes to next 8*bits bit boundary
 3681             // (this is a vestigial aspect of the compressed data format
 3682             // derived from an implementation that made use of a special VAX
 3683             // machine instruction!)
 3684             {
 3685                 unsigned rem = ((g.in_tot - g.in_left) - mark) % bits;
 3686                 if (rem) {
 3687                     rem = bits - rem;
 3688                     if (NOMORE())
 3689                         break;              // end of compressed data
 3690                     while (rem > g.in_left) {
 3691                         rem -= g.in_left;
 3692                         if (load() == 0)
 3693                             throw(EDOM, "%s: lzw premature end", g.inf);
 3694                     }
 3695                     g.in_left -= rem;
 3696                     g.in_next += rem;
 3697                 }
 3698             }
 3699             buf = 0;
 3700             left = 0;
 3701 
 3702             // mark this new location for computing the next flush
 3703             mark = g.in_tot - g.in_left;
 3704 
 3705             // go to the next number of bits per symbol
 3706             bits++;
 3707             mask <<= 1;
 3708             mask++;
 3709         }
 3710 
 3711         // get a code of bits bits
 3712         if (NOMORE())
 3713             break;                          // end of compressed data
 3714         buf += (bits_t)(NEXT()) << left;
 3715         left += 8;
 3716         if (left < bits) {
 3717             if (NOMORE())
 3718                 throw(EDOM, "%s: lzw premature end", g.inf);
 3719             buf += (bits_t)(NEXT()) << left;
 3720             left += 8;
 3721         }
 3722         code = buf & mask;
 3723         buf >>= bits;
 3724         left -= bits;
 3725 
 3726         // process clear code (256)
 3727         if (code == 256 && flags) {
 3728             // flush unused input bits and bytes to next 8*bits bit boundary
 3729             {
 3730                 unsigned rem = ((g.in_tot - g.in_left) - mark) % bits;
 3731                 if (rem) {
 3732                     rem = bits - rem;
 3733                     while (rem > g.in_left) {
 3734                         rem -= g.in_left;
 3735                         if (load() == 0)
 3736                             throw(EDOM, "%s: lzw premature end", g.inf);
 3737                     }
 3738                     g.in_left -= rem;
 3739                     g.in_next += rem;
 3740                 }
 3741             }
 3742             buf = 0;
 3743             left = 0;
 3744 
 3745             // mark this new location for computing the next flush
 3746             mark = g.in_tot - g.in_left;
 3747 
 3748             // go back to nine bits per symbol
 3749             bits = 9;                       // initialize bits and mask
 3750             mask = 0x1ff;
 3751             end = 255;                      // empty table
 3752             continue;                       // get next code
 3753         }
 3754 
 3755         // special code to reuse last match
 3756         {
 3757             unsigned temp = code;           // save the current code
 3758             if (code > end) {
 3759                 // be picky on the allowed code here, and make sure that the
 3760                 // code we drop through (prev) will be a valid index so that
 3761                 // random input does not cause an exception
 3762                 if (code != end + 1 || prev > end)
 3763                     throw(EDOM, "%s: invalid lzw code", g.inf);
 3764                 match[stack++] = (unsigned char)final;
 3765                 code = prev;
 3766             }
 3767 
 3768             // walk through linked list to generate output in reverse order
 3769             while (code >= 256) {
 3770                 match[stack++] = suffix[code];
 3771                 code = prefix[code];
 3772             }
 3773             match[stack++] = (unsigned char)code;
 3774             final = code;
 3775 
 3776             // link new table entry
 3777             if (end < mask) {
 3778                 end++;
 3779                 prefix[end] = (uint_least16_t)prev;
 3780                 suffix[end] = (unsigned char)final;
 3781             }
 3782 
 3783             // set previous code for next iteration
 3784             prev = temp;
 3785         }
 3786 
 3787         // write output in forward order
 3788         while (stack > OUTSIZE - outcnt) {
 3789             while (outcnt < OUTSIZE)
 3790                 out_buf[outcnt++] = match[--stack];
 3791             g.out_tot += outcnt;
 3792             if (g.decode == 1)
 3793                 writen(g.outd, out_buf, outcnt);
 3794             outcnt = 0;
 3795         }
 3796         do {
 3797             out_buf[outcnt++] = match[--stack];
 3798         } while (stack);
 3799     }
 3800 
 3801     // write any remaining buffered output
 3802     g.out_tot += outcnt;
 3803     if (outcnt && g.decode == 1)
 3804         writen(g.outd, out_buf, outcnt);
 3805 }
 3806 
 3807 // --- file processing ---
 3808 
 3809 // Extract file name from path.
 3810 local char *justname(char *path) {
 3811     char *p;
 3812 
 3813     p = strrchr(path, '/');
 3814     return p == NULL ? path : p + 1;
 3815 }
 3816 
 3817 // Copy file attributes, from -> to, as best we can. This is best effort, so no
 3818 // errors are reported. The mode bits, including suid, sgid, and the sticky bit
 3819 // are copied (if allowed), the owner's user id and group id are copied (again
 3820 // if allowed), and the access and modify times are copied.
 3821 local int copymeta(char *from, char *to) {
 3822     struct stat st;
 3823     struct timeval times[2];
 3824 
 3825     // get all of from's Unix meta data, return if not a regular file
 3826     if (stat(from, &st) != 0 || (st.st_mode & S_IFMT) != S_IFREG)
 3827         return -4;
 3828 
 3829     // set to's mode bits, ignore errors
 3830     int ret = chmod(to, st.st_mode & 07777);
 3831 
 3832     // copy owner's user and group, ignore errors
 3833     ret += chown(to, st.st_uid, st.st_gid);
 3834 
 3835     // copy access and modify times, ignore errors
 3836     times[0].tv_sec = st.st_atime;
 3837     times[0].tv_usec = 0;
 3838     times[1].tv_sec = st.st_mtime;
 3839     times[1].tv_usec = 0;
 3840     ret += utimes(to, times);
 3841     return ret;
 3842 }
 3843 
 3844 // Set the access and modify times of fd to t.
 3845 local void touch(char *path, time_t t) {
 3846     struct timeval times[2];
 3847 
 3848     times[0].tv_sec = t;
 3849     times[0].tv_usec = 0;
 3850     times[1].tv_sec = t;
 3851     times[1].tv_usec = 0;
 3852     (void)utimes(path, times);
 3853 }
 3854 
 3855 // Request that all data buffered by the operating system for g.outd be written
 3856 // to the permanent storage device. If fsync(fd) is used (POSIX), then all of
 3857 // the data is sent to the device, but will likely be buffered in volatile
 3858 // memory on the device itself, leaving open a window of vulnerability.
 3859 // fcntl(fd, F_FULLSYNC) on the other hand, available in macOS only, will
 3860 // request and wait for the device to write out its buffered data to permanent
 3861 // storage. On Windows, _commit() is used.
 3862 local void out_push(void) {
 3863     if (g.outd == -1)
 3864         return;
 3865 #if defined(F_FULLSYNC)
 3866     int ret = fcntl(g.outd, F_FULLSYNC);
 3867 #elif defined(_WIN32)
 3868     int ret = _commit(g.outd);
 3869 #else
 3870     int ret = fsync(g.outd);
 3871 #endif
 3872     if (ret == -1)
 3873         throw(errno, "sync error on %s (%s)", g.outf, strerror(errno));
 3874 }
 3875 
 3876 // Process provided input file, or stdin if path is NULL. process() can call
 3877 // itself for recursive directory processing.
 3878 local void process(char *path) {
 3879     volatile int method = -1;       // get_header() return value
 3880     size_t len;                     // length of base name (minus suffix)
 3881     struct stat st;                 // to get file type and mod time
 3882     ball_t err;                     // error information from throw()
 3883     // all compressed suffixes for decoding search, in length order
 3884     static char *sufs[] = {".z", "-z", "_z", ".Z", ".gz", "-gz", ".zz", "-zz",
 3885                            ".zip", ".ZIP", ".tgz", NULL};
 3886 
 3887     // open input file with name in, descriptor ind -- set name and mtime
 3888     if (path == NULL) {
 3889         vstrcpy(&g.inf, &g.inz, 0, "<stdin>");
 3890         g.ind = 0;
 3891         g.name = NULL;
 3892         g.mtime = g.headis & 2 ?
 3893                   (fstat(g.ind, &st) ? time(NULL) : st.st_mtime) : 0;
 3894         len = 0;
 3895     }
 3896     else {
 3897         // set input file name (already set if recursed here)
 3898         if (path != g.inf)
 3899             vstrcpy(&g.inf, &g.inz, 0, path);
 3900         len = strlen(g.inf);
 3901 
 3902         // try to stat input file -- if not there and decoding, look for that
 3903         // name with compressed suffixes
 3904         if (lstat(g.inf, &st)) {
 3905             if (errno == ENOENT && (g.list || g.decode)) {
 3906                 char **sufx = sufs;
 3907                 do {
 3908                     if (*sufx == NULL)
 3909                         break;
 3910                     vstrcpy(&g.inf, &g.inz, len, *sufx++);
 3911                     errno = 0;
 3912                 } while (lstat(g.inf, &st) && errno == ENOENT);
 3913             }
 3914 #if defined(EOVERFLOW) && defined(EFBIG)
 3915             if (errno == EOVERFLOW || errno == EFBIG)
 3916                 throw(EDOM, "%s too large -- "
 3917                       "not compiled with large file support", g.inf);
 3918 #endif
 3919             if (errno) {
 3920                 g.inf[len] = 0;
 3921                 complain("skipping: %s does not exist", g.inf);
 3922                 return;
 3923             }
 3924             len = strlen(g.inf);
 3925         }
 3926 
 3927         // only process regular files or named pipes, but allow symbolic links
 3928         // if -f, recurse into directory if -r
 3929         if ((st.st_mode & S_IFMT) != S_IFREG &&
 3930             (st.st_mode & S_IFMT) != S_IFIFO &&
 3931             (st.st_mode & S_IFMT) != S_IFLNK &&
 3932             (st.st_mode & S_IFMT) != S_IFDIR) {
 3933             complain("skipping: %s is a special file or device", g.inf);
 3934             return;
 3935         }
 3936         if ((st.st_mode & S_IFMT) == S_IFLNK && !g.force && !g.pipeout) {
 3937             complain("skipping: %s is a symbolic link", g.inf);
 3938             return;
 3939         }
 3940         if ((st.st_mode & S_IFMT) == S_IFDIR && !g.recurse) {
 3941             complain("skipping: %s is a directory", g.inf);
 3942             return;
 3943         }
 3944 
 3945         // recurse into directory (assumes Unix)
 3946         if ((st.st_mode & S_IFMT) == S_IFDIR) {
 3947             char *roll = NULL;
 3948             size_t size = 0, off = 0, base;
 3949             DIR *here;
 3950             struct dirent *next;
 3951 
 3952             // accumulate list of entries (need to do this, since readdir()
 3953             // behavior not defined if directory modified between calls)
 3954             here = opendir(g.inf);
 3955             if (here == NULL)
 3956                 return;
 3957             while ((next = readdir(here)) != NULL) {
 3958                 if (next->d_name[0] == 0 ||
 3959                     (next->d_name[0] == '.' && (next->d_name[1] == 0 ||
 3960                      (next->d_name[1] == '.' && next->d_name[2] == 0))))
 3961                     continue;
 3962                 off = vstrcpy(&roll, &size, off, next->d_name);
 3963             }
 3964             closedir(here);
 3965             vstrcpy(&roll, &size, off, "");
 3966 
 3967             // run process() for each entry in the directory
 3968             base = len && g.inf[len - 1] != (unsigned char)'/' ?
 3969                    vstrcpy(&g.inf, &g.inz, len, "/") - 1 : len;
 3970             for (off = 0; roll[off]; off += strlen(roll + off) + 1) {
 3971                 vstrcpy(&g.inf, &g.inz, base, roll + off);
 3972                 process(g.inf);
 3973             }
 3974             g.inf[len] = 0;
 3975 
 3976             // release list of entries
 3977             FREE(roll);
 3978             return;
 3979         }
 3980 
 3981         // don't compress .gz (or provided suffix) files, unless -f
 3982         if (!(g.force || g.list || g.decode) && len >= strlen(g.sufx) &&
 3983                 strcmp(g.inf + len - strlen(g.sufx), g.sufx) == 0) {
 3984             complain("skipping: %s ends with %s", g.inf, g.sufx);
 3985             return;
 3986         }
 3987 
 3988         // create output file only if input file has compressed suffix
 3989         if (g.decode == 1 && !g.pipeout && !g.list) {
 3990             size_t suf = compressed_suffix(g.inf);
 3991             if (suf == 0) {
 3992                 complain("skipping: %s does not have compressed suffix",
 3993                          g.inf);
 3994                 return;
 3995             }
 3996             len -= suf;
 3997         }
 3998 
 3999         // open input file
 4000         g.ind = open(g.inf, O_RDONLY, 0);
 4001         if (g.ind < 0)
 4002             throw(errno, "read error on %s (%s)", g.inf, strerror(errno));
 4003 
 4004         // prepare gzip header information for compression
 4005         g.name = g.headis & 1 ? justname(g.inf) : NULL;
 4006         g.mtime = g.headis & 2 ? st.st_mtime : 0;
 4007     }
 4008     SET_BINARY_MODE(g.ind);
 4009 
 4010     // if decoding or testing, try to read gzip header
 4011     if (g.decode) {
 4012         in_init();
 4013         method = get_header(1);
 4014         if (method != 8 && method != 257 &&
 4015                 // gzip -cdf acts like cat on uncompressed input
 4016                 !((method == -1 || method == -2) && g.force && g.pipeout &&
 4017                   g.decode != 2 && !g.list)) {
 4018             load_end();
 4019             complain(method == -6 ? "skipping: %s corrupt: header crc error" :
 4020                      method == -1 ? "skipping: %s empty" :
 4021                      method < 0 ? "skipping: %s unrecognized format" :
 4022                      "skipping: %s unknown compression method", g.inf);
 4023             return;
 4024         }
 4025 
 4026         // if requested, test input file (possibly a test list)
 4027         if (g.decode == 2) {
 4028             try {
 4029                 if (method == 8)
 4030                     infchk();
 4031                 else {
 4032                     unlzw();
 4033                     if (g.list) {
 4034                         g.in_tot -= 3;
 4035                         show_info(method, 0, g.out_tot, 0);
 4036                     }
 4037                 }
 4038             }
 4039             catch (err) {
 4040                 if (err.code != EDOM)
 4041                     punt(err);
 4042                 complain("skipping: %s", err.why);
 4043                 drop(err);
 4044                 outb(NULL, NULL, 0);
 4045             }
 4046             load_end();
 4047             return;
 4048         }
 4049     }
 4050 
 4051     // if requested, just list information about input file
 4052     if (g.list) {
 4053         list_info();
 4054         load_end();
 4055         return;
 4056     }
 4057 
 4058     // create output file out, descriptor outd
 4059     if (path == NULL || g.pipeout) {
 4060         // write to stdout
 4061         g.outf = alloc(NULL, strlen("<stdout>") + 1);
 4062         strcpy(g.outf, "<stdout>");
 4063         g.outd = 1;
 4064         if (!g.decode && !g.force && isatty(g.outd))
 4065             throw(EINVAL, "trying to write compressed data to a terminal"
 4066                           " (use -f to force)");
 4067     }
 4068     else {
 4069         char *to = g.inf, *sufx = "";
 4070         size_t pre = 0;
 4071 
 4072         // select parts of the output file name
 4073         if (g.decode) {
 4074             // for -dN or -dNT, use the path from the input file and the name
 4075             // from the header, stripping any path in the header name
 4076             if ((g.headis & 1) != 0 && g.hname != NULL) {
 4077                 pre = (size_t)(justname(g.inf) - g.inf);
 4078                 to = justname(g.hname);
 4079                 len = strlen(to);
 4080             }
 4081             // for -d or -dNn, replace abbreviated suffixes
 4082             else if (strcmp(to + len, ".tgz") == 0)
 4083                 sufx = ".tar";
 4084         }
 4085         else
 4086             // add appropriate suffix when compressing
 4087             sufx = g.sufx;
 4088 
 4089         // create output file and open to write, overwriting any existing file
 4090         // of the same name only if requested with --force or -f
 4091         g.outf = alloc(NULL, pre + len + strlen(sufx) + 1);
 4092         memcpy(g.outf, g.inf, pre);
 4093         memcpy(g.outf + pre, to, len);
 4094         strcpy(g.outf + pre + len, sufx);
 4095         g.outd = open(g.outf, O_CREAT | O_TRUNC | O_WRONLY |
 4096                               (g.force ? 0 : O_EXCL), 0600);
 4097 
 4098         // if it exists and wasn't forced, give the user a chance to overwrite
 4099         if (g.outd < 0 && errno == EEXIST) {
 4100             int overwrite = 0;
 4101             if (isatty(0) && g.verbosity) {
 4102                 // get a response from the user -- the first non-blank
 4103                 // character has to be a "y" or a "Y" to permit an overwrite
 4104                 fprintf(stderr, "%s exists -- overwrite (y/n)? ", g.outf);
 4105                 fflush(stderr);
 4106                 int ch, first = 1;
 4107                 do {
 4108                     ch = getchar();
 4109                     if (first == 1) {
 4110                         if (ch == ' ' || ch == '\t')
 4111                             continue;
 4112                         if (ch == 'y' || ch == 'Y')
 4113                             overwrite = 1;
 4114                         first = 0;
 4115                     }
 4116                 } while (ch != EOF && ch != '\n' && ch != '\r');
 4117             }
 4118             if (!overwrite) {
 4119                 complain("skipping: %s exists", g.outf);
 4120                 RELEASE(g.outf);
 4121                 load_end();
 4122                 return;
 4123             }
 4124             g.outd = open(g.outf, O_CREAT | O_TRUNC | O_WRONLY, 0600);
 4125         }
 4126 
 4127         // if some other error, give up
 4128         if (g.outd < 0)
 4129             throw(errno, "write error on %s (%s)", g.outf, strerror(errno));
 4130     }
 4131     SET_BINARY_MODE(g.outd);
 4132 
 4133     // process ind to outd
 4134     if (g.verbosity > 1)
 4135         fprintf(stderr, "%s to %s ", g.inf, g.outf);
 4136     if (g.decode) {
 4137         try {
 4138             if (method == 8)
 4139                 infchk();
 4140             else if (method == 257)
 4141                 unlzw();
 4142             else
 4143                 cat();
 4144         }
 4145         catch (err) {
 4146             if (err.code != EDOM)
 4147                 punt(err);
 4148             complain("skipping: %s", err.why);
 4149             drop(err);
 4150             outb(NULL, NULL, 0);
 4151             if (g.outd != -1 && g.outd != 1) {
 4152                 close(g.outd);
 4153                 g.outd = -1;
 4154                 unlink(g.outf);
 4155                 RELEASE(g.outf);
 4156             }
 4157         }
 4158     }
 4159 #ifndef NOTHREAD
 4160     else if (g.procs > 1)
 4161         parallel_compress();
 4162 #endif
 4163     else
 4164         single_compress(0);
 4165     if (g.verbosity > 1) {
 4166         putc('\n', stderr);
 4167         fflush(stderr);
 4168     }
 4169 
 4170     // finish up, copy attributes, set times, delete original
 4171     load_end();
 4172     if (g.outd != -1 && g.outd != 1) {
 4173         if (g.sync)
 4174             out_push();         // push to permanent storage
 4175         if (close(g.outd))
 4176             throw(errno, "write error on %s (%s)", g.outf, strerror(errno));
 4177         g.outd = -1;            // now prevent deletion on interrupt
 4178         if (g.ind != 0) {
 4179             copymeta(g.inf, g.outf);
 4180             if (!g.keep)
 4181                 unlink(g.inf);
 4182         }
 4183         if (g.decode && (g.headis & 2) != 0 && g.stamp)
 4184             touch(g.outf, g.stamp);
 4185     }
 4186     RELEASE(g.outf);
 4187 }
 4188 
 4189 local char *helptext[] = {
 4190 "Usage: pigz [options] [files ...]",
 4191 "  will compress files in place, adding the suffix '.gz'. If no files are",
 4192 #ifdef NOTHREAD
 4193 "  specified, stdin will be compressed to stdout. pigz does what gzip does.",
 4194 #else
 4195 "  specified, stdin will be compressed to stdout. pigz does what gzip does,",
 4196 "  but spreads the work over multiple processors and cores when compressing.",
 4197 #endif
 4198 "",
 4199 "Options:",
 4200 #ifdef NOZOPFLI
 4201 "  -0 to -9             Compression level",
 4202 #else
 4203 "  -0 to -9, -11        Compression level (level 11, zopfli, is much slower)",
 4204 #endif
 4205 "  --fast, --best       Compression levels 1 and 9 respectively",
 4206 "  -A, --alias xxx      Use xxx as the name for any --zip entry from stdin",
 4207 "  -b, --blocksize mmm  Set compression block size to mmmK (default 128K)",
 4208 "  -c, --stdout         Write all processed output to stdout (won't delete)",
 4209 "  -C, --comment ccc    Put comment ccc in the gzip or zip header",
 4210 "  -d, --decompress     Decompress the compressed input",
 4211 "  -f, --force          Force overwrite, compress .gz, links, and to terminal",
 4212 #ifndef NOZOPFLI
 4213 "  -F  --first          Do iterations first, before block split for -11",
 4214 #endif
 4215 "  -h, --help           Display a help screen and quit",
 4216 "  -H, --huffman        Use only Huffman coding for compression",
 4217 "  -i, --independent    Compress blocks independently for damage recovery",
 4218 #ifndef NOZOPFLI
 4219 "  -I, --iterations n   Number of iterations for -11 optimization",
 4220 "  -J, --maxsplits n    Maximum number of split blocks for -11",
 4221 #endif
 4222 "  -k, --keep           Do not delete original file after processing",
 4223 "  -K, --zip            Compress to PKWare zip (.zip) single entry format",
 4224 "  -l, --list           List the contents of the compressed input",
 4225 "  -L, --license        Display the pigz license and quit",
 4226 "  -m, --no-time        Do not store or restore mod time",
 4227 "  -M, --time           Store or restore mod time",
 4228 "  -n, --no-name        Do not store or restore file name or mod time",
 4229 "  -N, --name           Store or restore file name and mod time",
 4230 #ifndef NOZOPFLI
 4231 "  -O  --oneblock       Do not split into smaller blocks for -11",
 4232 #endif
 4233 #ifndef NOTHREAD
 4234 "  -p, --processes n    Allow up to n compression threads (default is the",
 4235 "                       number of online processors, or 8 if unknown)",
 4236 #endif
 4237 "  -q, --quiet          Print no messages, even on error",
 4238 "  -r, --recursive      Process the contents of all subdirectories",
 4239 "  -R, --rsyncable      Input-determined block locations for rsync",
 4240 "  -S, --suffix .sss    Use suffix .sss instead of .gz (for compression)",
 4241 "  -t, --test           Test the integrity of the compressed input",
 4242 "  -U, --rle            Use run-length encoding for compression",
 4243 #ifdef PIGZ_DEBUG
 4244 "  -v, --verbose        Provide more verbose output (-vv to debug)",
 4245 #else
 4246 "  -v, --verbose        Provide more verbose output",
 4247 #endif
 4248 "  -V  --version        Show the version of pigz",
 4249 "  -Y  --synchronous    Force output file write to permanent storage",
 4250 "  -z, --zlib           Compress to zlib (.zz) instead of gzip format",
 4251 "  --                   All arguments after \"--\" are treated as files"
 4252 };
 4253 
 4254 // Display the help text above.
 4255 local void help(void) {
 4256     int n;
 4257 
 4258     if (g.verbosity == 0)
 4259         return;
 4260     for (n = 0; n < (int)(sizeof(helptext) / sizeof(char *)); n++)
 4261         fprintf(stderr, "%s\n", helptext[n]);
 4262     fflush(stderr);
 4263     exit(0);
 4264 }
 4265 
 4266 #ifndef NOTHREAD
 4267 
 4268 // Try to determine the number of processors.
 4269 local int nprocs(int n) {
 4270 #  ifdef _SC_NPROCESSORS_ONLN
 4271     n = (int)sysconf(_SC_NPROCESSORS_ONLN);
 4272 #  else
 4273 #    ifdef _SC_NPROC_ONLN
 4274     n = (int)sysconf(_SC_NPROC_ONLN);
 4275 #    else
 4276 #      ifdef __hpux
 4277     struct pst_dynamic psd;
 4278 
 4279     if (pstat_getdynamic(&psd, sizeof(psd), (size_t)1, 0) != -1)
 4280         n = psd.psd_proc_cnt;
 4281 #      endif
 4282 #    endif
 4283 #  endif
 4284     return n;
 4285 }
 4286 
 4287 #endif
 4288 
 4289 // Set option defaults.
 4290 local void defaults(void) {
 4291     g.level = Z_DEFAULT_COMPRESSION;
 4292     g.strategy = Z_DEFAULT_STRATEGY;
 4293 #ifndef NOZOPFLI
 4294     // default zopfli options as set by ZopfliInitOptions():
 4295     //  verbose = 0
 4296     //  numiterations = 15
 4297     //  blocksplitting = 1
 4298     //  blocksplittinglast = 0
 4299     //  blocksplittingmax = 15
 4300     ZopfliInitOptions(&g.zopts);
 4301 #endif
 4302     g.block = 131072UL;             // 128K
 4303 #ifdef NOTHREAD
 4304     g.procs = 1;
 4305 #else
 4306     g.procs = nprocs(8);
 4307     g.shift = x2nmodp(g.block, 3);
 4308 #endif
 4309     g.rsync = 0;                    // don't do rsync blocking
 4310     g.setdict = 1;                  // initialize dictionary each thread
 4311     g.verbosity = 1;                // normal message level
 4312     g.headis = 3;                   // store name and time (low bits == 11),
 4313                                     // restore neither (next bits == 00),
 4314                                     // where 01 is name and 10 is time
 4315     g.pipeout = 0;                  // don't force output to stdout
 4316     g.sufx = ".gz";                 // compressed file suffix
 4317     g.comment = NULL;               // no comment
 4318     g.decode = 0;                   // compress
 4319     g.list = 0;                     // compress
 4320     g.keep = 0;                     // delete input file once compressed
 4321     g.force = 0;                    // don't overwrite, don't compress links
 4322     g.sync = 0;                     // don't force a flush on output
 4323     g.recurse = 0;                  // don't go into directories
 4324     g.form = 0;                     // use gzip format
 4325 }
 4326 
 4327 // Long options conversion to short options.
 4328 local char *longopts[][2] = {
 4329     {"LZW", "Z"}, {"lzw", "Z"}, {"alias", "A"}, {"ascii", "a"}, {"best", "9"},
 4330     {"bits", "Z"}, {"blocksize", "b"}, {"decompress", "d"}, {"fast", "1"},
 4331     {"force", "f"}, {"comment", "C"},
 4332 #ifndef NOZOPFLI
 4333     {"first", "F"}, {"iterations", "I"}, {"maxsplits", "J"}, {"oneblock", "O"},
 4334 #endif
 4335     {"help", "h"}, {"independent", "i"}, {"keep", "k"}, {"license", "L"},
 4336     {"list", "l"}, {"name", "N"}, {"no-name", "n"}, {"no-time", "m"},
 4337     {"processes", "p"}, {"quiet", "q"}, {"recursive", "r"}, {"rsyncable", "R"},
 4338     {"silent", "q"}, {"stdout", "c"}, {"suffix", "S"}, {"synchronous", "Y"},
 4339     {"test", "t"}, {"time", "M"}, {"to-stdout", "c"}, {"uncompress", "d"},
 4340     {"verbose", "v"}, {"version", "V"}, {"zip", "K"}, {"zlib", "z"},
 4341     {"huffman", "H"}, {"rle", "U"}};
 4342 #define NLOPTS (sizeof(longopts) / (sizeof(char *) << 1))
 4343 
 4344 // Either new buffer size, new compression level, or new number of processes.
 4345 // Get rid of old buffers and threads to force the creation of new ones with
 4346 // the new settings.
 4347 local void new_opts(void) {
 4348     single_compress(1);
 4349 #ifndef NOTHREAD
 4350     finish_jobs();
 4351 #endif
 4352 }
 4353 
 4354 // Verify that arg is only digits, and if so, return the decimal value.
 4355 local size_t num(char *arg) {
 4356     char *str = arg;
 4357     size_t val = 0;
 4358 
 4359     if (*str == 0)
 4360         throw(EINVAL, "internal error: empty parameter");
 4361     do {
 4362         if (*str < '0' || *str > '9' ||
 4363             (val && ((~(size_t)0) - (size_t)(*str - '0')) / val < 10))
 4364             throw(EINVAL, "invalid numeric parameter: %s", arg);
 4365         val = val * 10 + (size_t)(*str - '0');
 4366     } while (*++str);
 4367     return val;
 4368 }
 4369 
 4370 // Process an argument, return true if it is an option (not a filename)
 4371 local int option(char *arg) {
 4372     static int get = 0;     // if not zero, look for option parameter
 4373     char bad[3] = "-X";     // for error messages (X is replaced)
 4374 
 4375     // if no argument or dash option, check status of get
 4376     if (get && (arg == NULL || *arg == '-')) {
 4377         bad[1] = "bpSIJAC"[get - 1];
 4378         throw(EINVAL, "missing parameter after %s", bad);
 4379     }
 4380     if (arg == NULL)
 4381         return 1;
 4382 
 4383     // process long option or short options
 4384     if (*arg == '-') {
 4385         // a single dash will be interpreted as stdin
 4386         if (*++arg == 0)
 4387             return 0;
 4388 
 4389         // process long option (fall through with equivalent short option)
 4390         if (*arg == '-') {
 4391             int j;
 4392 
 4393             arg++;
 4394             for (j = NLOPTS - 1; j >= 0; j--)
 4395                 if (strcmp(arg, longopts[j][0]) == 0) {
 4396                     arg = longopts[j][1];
 4397                     break;
 4398                 }
 4399             if (j < 0)
 4400                 throw(EINVAL, "invalid option: %s", arg - 2);
 4401         }
 4402 
 4403         // process short options (more than one allowed after dash)
 4404         do {
 4405             // if looking for a parameter, don't process more single character
 4406             // options until we have the parameter
 4407             if (get) {
 4408                 if (get == 3)
 4409                     throw(EINVAL,
 4410                           "invalid usage: -S must be followed by space");
 4411                 if (get == 7)
 4412                     throw(EINVAL,
 4413                           "invalid usage: -C must be followed by space");
 4414                 break;      // allow -*nnn to fall to parameter code
 4415             }
 4416 
 4417             // process next single character option or compression level
 4418             bad[1] = *arg;
 4419             switch (*arg) {
 4420             case '0': case '1': case '2': case '3': case '4':
 4421             case '5': case '6': case '7': case '8': case '9':
 4422                 g.level = *arg - '0';
 4423                 while (arg[1] >= '0' && arg[1] <= '9') {
 4424                     if (g.level && (INT_MAX - (arg[1] - '0')) / g.level < 10)
 4425                         throw(EINVAL, "only levels 0..9 and 11 are allowed");
 4426                     g.level = g.level * 10 + *++arg - '0';
 4427                 }
 4428                 if (g.level == 10 || g.level > 11)
 4429                     throw(EINVAL, "only levels 0..9 and 11 are allowed");
 4430                 break;
 4431             case 'A':  get = 6;  break;
 4432             case 'C':  get = 7;  break;
 4433 #ifndef NOZOPFLI
 4434             case 'F':  g.zopts.blocksplittinglast = 1;  break;
 4435             case 'I':  get = 4;  break;
 4436             case 'H':  g.strategy = Z_HUFFMAN_ONLY;  break;
 4437             case 'J':  get = 5;  break;
 4438 #endif
 4439             case 'K':  g.form = 2;  g.sufx = ".zip";  break;
 4440             case 'L':
 4441                 puts(VERSION);
 4442                 puts("Copyright (C) 2007-2021 Mark Adler");
 4443                 puts("Subject to the terms of the zlib license.");
 4444                 puts("No warranty is provided or implied.");
 4445                 exit(0);
 4446                 break;          // avoid warning
 4447             case 'M':  g.headis |= 0xa;  break;
 4448             case 'N':  g.headis = 0xf;  break;
 4449 #ifndef NOZOPFLI
 4450             case 'O':  g.zopts.blocksplitting = 0;  break;
 4451 #endif
 4452             case 'R':  g.rsync = 1;  break;
 4453             case 'S':  get = 3;  break;
 4454                 // -T defined below as an alternative for -m
 4455             case 'V':
 4456                 puts(VERSION);
 4457                 if (g.verbosity > 1)
 4458                     printf("zlib %s\n", zlibVersion());
 4459                 exit(0);
 4460                 break;          // avoid warning
 4461             case 'Y':  g.sync = 1;  break;
 4462             case 'Z':
 4463                 throw(EINVAL, "invalid option: LZW output not supported: %s",
 4464                       bad);
 4465                 break;          // avoid warning
 4466             case 'a':
 4467                 throw(EINVAL, "invalid option: no ascii conversion: %s",
 4468                       bad);
 4469                 break;          // avoid warning
 4470             case 'b':  get = 1;  break;
 4471             case 'c':  g.pipeout = 1;  break;
 4472             case 'd':  if (!g.decode) g.headis >>= 2;  g.decode = 1;  break;
 4473             case 'f':  g.force = 1;  break;
 4474             case 'h':  help();  break;
 4475             case 'i':  g.setdict = 0;  break;
 4476             case 'k':  g.keep = 1;  break;
 4477             case 'l':  g.list = 1;  break;
 4478             case 'n':  g.headis = 0;  break;
 4479             case 'T':
 4480             case 'm':  g.headis &= ~0xa;  break;
 4481             case 'p':  get = 2;  break;
 4482             case 'q':  g.verbosity = 0;  break;
 4483             case 'r':  g.recurse = 1;  break;
 4484             case 't':  g.decode = 2;  break;
 4485             case 'U':  g.strategy = Z_RLE;  break;
 4486             case 'v':  g.verbosity++;  break;
 4487             case 'z':  g.form = 1;  g.sufx = ".zz";  break;
 4488             default:
 4489                 throw(EINVAL, "invalid option: %s", bad);
 4490             }
 4491         } while (*++arg);
 4492         if (*arg == 0)
 4493             return 1;
 4494     }
 4495 
 4496     // process option parameter for -b, -p, -A, -S, -I, or -J
 4497     if (get) {
 4498         size_t n;
 4499 
 4500         if (get == 1) {
 4501             n = num(arg);
 4502             g.block = n << 10;                  // chunk size
 4503 #ifndef NOTHREAD
 4504             g.shift = x2nmodp(g.block, 3);
 4505 #endif
 4506             if (g.block < DICT)
 4507                 throw(EINVAL, "block size too small (must be >= 32K)");
 4508             if (n != g.block >> 10 ||
 4509                 OUTPOOL(g.block) < g.block ||
 4510                 (ssize_t)OUTPOOL(g.block) < 0 ||
 4511                 g.block > (1UL << 29))          // limited by append_len()
 4512                 throw(EINVAL, "block size too large: %s", arg);
 4513         }
 4514         else if (get == 2) {
 4515             n = num(arg);
 4516             g.procs = (int)n;                   // # processes
 4517             if (g.procs < 1)
 4518                 throw(EINVAL, "invalid number of processes: %s", arg);
 4519             if ((size_t)g.procs != n || INBUFS(g.procs) < 1)
 4520                 throw(EINVAL, "too many processes: %s", arg);
 4521 #ifdef NOTHREAD
 4522             if (g.procs > 1)
 4523                 throw(EINVAL, "compiled without threads");
 4524 #endif
 4525         }
 4526         else if (get == 3) {
 4527             if (*arg == 0)
 4528                 throw(EINVAL, "suffix cannot be empty");
 4529             g.sufx = arg;                       // gz suffix
 4530         }
 4531 #ifndef NOZOPFLI
 4532         else if (get == 4)
 4533             g.zopts.numiterations = (int)num(arg);  // optimize iterations
 4534         else if (get == 5)
 4535             g.zopts.blocksplittingmax = (int)num(arg);  // max block splits
 4536         else if (get == 6)
 4537             g.alias = arg;                      // zip name for stdin
 4538 #endif
 4539         else if (get == 7)
 4540             g.comment = arg;                    // header comment
 4541         get = 0;
 4542         return 1;
 4543     }
 4544 
 4545     // neither an option nor parameter
 4546     return 0;
 4547 }
 4548 
 4549 #ifndef NOTHREAD
 4550 // handle error received from yarn function
 4551 local void cut_yarn(int err) {
 4552     throw(err, "internal threads error");
 4553 }
 4554 #endif
 4555 
 4556 // Process command line arguments.
 4557 int main(int argc, char **argv) {
 4558     int n;                          // general index
 4559     int nop;                        // index before which "-" means stdin
 4560     int done;                       // number of named files processed
 4561     size_t k;                       // program name length
 4562     char *opts, *p;                 // environment default options, marker
 4563     ball_t err;                     // error information from throw()
 4564 
 4565     g.ret = 0;
 4566     try {
 4567         // initialize globals
 4568         g.inf = NULL;
 4569         g.inz = 0;
 4570 #ifndef NOTHREAD
 4571         g.in_which = -1;
 4572 #endif
 4573         g.alias = "-";
 4574         g.outf = NULL;
 4575         g.first = 1;
 4576         g.hname = NULL;
 4577         g.hcomm = NULL;
 4578 
 4579         // save pointer to program name for error messages
 4580         p = strrchr(argv[0], '/');
 4581         p = p == NULL ? argv[0] : p + 1;
 4582         g.prog = *p ? p : "pigz";
 4583 
 4584         // prepare for interrupts and logging
 4585         signal(SIGINT, cut_short);
 4586 #ifndef NOTHREAD
 4587         yarn_prefix = g.prog;           // prefix for yarn error messages
 4588         yarn_abort = cut_yarn;          // call on thread error
 4589 #endif
 4590 #ifdef PIGZ_DEBUG
 4591         gettimeofday(&start, NULL);     // starting time for log entries
 4592         log_init();                     // initialize logging
 4593 #endif
 4594 
 4595         // set all options to defaults
 4596         defaults();
 4597 
 4598         // check zlib version
 4599         if (zlib_vernum() < 0x1230)
 4600            throw(EINVAL, "zlib version less than 1.2.3");
 4601 
 4602         // create CRC table, in case zlib compiled with dynamic tables
 4603         get_crc_table();
 4604 
 4605         // process user environment variable defaults in GZIP
 4606         opts = getenv("GZIP");
 4607         if (opts != NULL) {
 4608             while (*opts) {
 4609                 while (*opts == ' ' || *opts == '\t')
 4610                     opts++;
 4611                 p = opts;
 4612                 while (*p && *p != ' ' && *p != '\t')
 4613                     p++;
 4614                 n = *p;
 4615                 *p = 0;
 4616                 if (!option(opts))
 4617                     throw(EINVAL, "cannot provide files in "
 4618                                   "GZIP environment variable");
 4619                 opts = p + (n ? 1 : 0);
 4620             }
 4621             option(NULL);           // check for missing parameter
 4622         }
 4623 
 4624         // process user environment variable defaults in PIGZ as well
 4625         opts = getenv("PIGZ");
 4626         if (opts != NULL) {
 4627             while (*opts) {
 4628                 while (*opts == ' ' || *opts == '\t')
 4629                     opts++;
 4630                 p = opts;
 4631                 while (*p && *p != ' ' && *p != '\t')
 4632                     p++;
 4633                 n = *p;
 4634                 *p = 0;
 4635                 if (!option(opts))
 4636                     throw(EINVAL, "cannot provide files in "
 4637                                   "PIGZ environment variable");
 4638                 opts = p + (n ? 1 : 0);
 4639             }
 4640             option(NULL);           // check for missing parameter
 4641         }
 4642 
 4643         // decompress if named "unpigz" or "gunzip", to stdout if "*cat"
 4644         if (strcmp(g.prog, "unpigz") == 0 || strcmp(g.prog, "gunzip") == 0) {
 4645             if (!g.decode)
 4646                 g.headis >>= 2;
 4647             g.decode = 1;
 4648         }
 4649         if ((k = strlen(g.prog)) > 2 && strcmp(g.prog + k - 3, "cat") == 0) {
 4650             if (!g.decode)
 4651                 g.headis >>= 2;
 4652             g.decode = 1;
 4653             g.pipeout = 1;
 4654         }
 4655 
 4656         // if no arguments and compressed data to/from terminal, show help
 4657         if (argc < 2 && isatty(g.decode ? 0 : 1))
 4658             help();
 4659 
 4660         // process all command-line options first
 4661         nop = argc;
 4662         for (n = 1; n < argc; n++)
 4663             if (strcmp(argv[n], "--") == 0) {
 4664                 nop = n;                // after this, "-" is the name "-"
 4665                 argv[n] = NULL;         // remove option
 4666                 break;                  // ignore options after "--"
 4667             }
 4668             else if (option(argv[n]))   // process argument
 4669                 argv[n] = NULL;         // remove if option
 4670         option(NULL);                   // check for missing parameter
 4671 
 4672         // process command-line filenames
 4673         done = 0;
 4674         for (n = 1; n < argc; n++)
 4675             if (argv[n] != NULL) {
 4676                 if (done == 1 && g.pipeout && !g.decode && !g.list &&
 4677                     g.form > 1)
 4678                     complain("warning: output will be concatenated zip files"
 4679                              " -- %s will not be able to extract", g.prog);
 4680                 process(n < nop && strcmp(argv[n], "-") == 0 ? NULL : argv[n]);
 4681                 done++;
 4682             }
 4683 
 4684         // list stdin or compress stdin to stdout if no file names provided
 4685         if (done == 0)
 4686             process(NULL);
 4687     }
 4688     always {
 4689         // release resources
 4690         RELEASE(g.inf);
 4691         g.inz = 0;
 4692         new_opts();
 4693     }
 4694     catch (err) {
 4695         THREADABORT(err);
 4696     }
 4697 
 4698     // show log (if any)
 4699     log_dump();
 4700     return g.ret;
 4701 }